题目描述

给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。

样例

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3

算法1

(迪杰斯特拉算法) $O(nlog_{2}n)$

直接套Dijkstra模板

时间复杂度 $O(nlog_{2}n)$

参考文献 无

C++ 代码

#include<bits/stdc++.h>
const int N=1e5+10,M=2e5+10,INF=0x3f3f3f3f;
int n,m,tot,x,y,z,first[N],ne[M],to[M],w[M],dis[N];
bool vis[N];
std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >,std::greater<std::pair<int,int> > >q;
void add(int x,int y,int z){
    ne[++tot]=first[x];
    first[x]=tot;
    to[tot]=y;
    w[tot]=z;
}
void dijkstra(){
    memset(dis,INF,sizeof(dis));
    dis[1]=0;
    q.push(std::make_pair(0,1));
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u]=true;
        for(int e=first[u];e;e=ne[e]){
            int v=to[e];
            if(dis[u]+w[e]<dis[v]){
                dis[v]=dis[u]+w[e];
                q.push(std::make_pair(dis[v],v));
            }
        }
    }
}
int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n>>m;
    while(m--){
        std::cin>>x>>y>>z;
        add(x,y,z);
    }
    dijkstra();
    if(dis[n]!=0x3f3f3f3f)std::cout<<dis[n]<<std::endl;
    else std::cout<<-1<<std::endl;
    return 0;
}