本文共 1259 字,大约阅读时间需要 4 分钟。
给定一个n个点m条边的有向图,图中可能存在重边和自环,所有边权均为非负值。
请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出-1。
输入格式
第一行包含整数n和m。接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。
输出格式
输出一个整数,表示1号点到n号点的最短距离。如果路径不存在,则输出-1。
数据范围
1≤n,m≤1.5×105, 图中涉及边长均不小于0,且不超过10000。输入样例:
3 3 1 2 2 2 3 1 1 3 4 输出样例: 3#include#include #include #include using namespace std;const int N=3e5+10;typedef pair PII;int ver[N],head[N],edge[N],ne[N], idx;bool st[N];//1 -> Nint dist[N];int n,m;int res;void add(int a,int b,int _edge) { edge[idx]=_edge; ver[idx]=b,ne[idx]=head[a],head[a]=idx++;}bool dijkstra() { priority_queue , greater > q; dist[1] =0; q.push({ 0,1}); while (q.size()) { auto xx = q.top();q.pop(); int _dist= xx.first, nod = xx.second; if (st[nod]) continue; st[nod] = true; for (int i=head[nod];i!=-1;i=ne[i]) { int _vertex = ver[i]; if (dist[_vertex] > dist[nod] + edge[i]) { dist[_vertex] = dist[nod] + edge[i]; q.push({ dist[_vertex], _vertex}); } } } if (dist[n]==0x3f3f3f3f) return false; res = dist[n]; return true;}int main() { memset(dist , 0x3f, sizeof dist); memset(head, -1, sizeof head); cin>>n>>m; while (m--) { int a,b,c;cin>>a>>b>>c; add(a,b,c); } if (dijkstra()) { cout << res; }else{ puts("-1"); } }
转载地址:http://wfyzi.baihongyu.com/