5779: 最短路
描述
给定 M 条边， N 个点的带权无向图。求 1到 N 的最短路。
输入
第一行：N,M(N≤100000，M≤500000)；
接下来M行3个正整数：ai,bi,ci表示ai,bi之间有一条长度为ci的路，ci≤1000。
输出
一个整数，表示 1 到 N 的最短距离。
样例输入
4 4
1 2 1
2 3 1
3 4 1
2 4 1
样例输出
2
提示
注意图中可能有重边和自环，数据保证 1 到 N 有路径相连。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+5,inf = 0x3f; 4 struct node{ 5 int to,d; 6 }; 7 int dis[N],vis[N]; 8 vector<node> g[N]; 9 void spfa(int u) 10 { 11 queue<int> q; 12 memset(vis,0,sizeof(vis)); 13 memset(dis,inf,sizeof(dis)); 14 dis[u] = 0;vis[u] = 1; 15 q.push(u); 16 while(!q.empty()) 17 { 18 int f = q.front();q.pop(); 19 vis[f] = 0; //先清空队首标记 20 for(int i=0;i<g[f].size();i++) //遍历和f结点相连的结点 21 { 22 node v = g[f][i]; 23 if(v.d+dis[f]<dis[v.to])//如果起点u到f+f到i的距离v.d < 起点到i的距离v.to，那么更新 24 { 25 dis[v.to] = v.d+dis[f]; 26 if(vis[v.to]==0) //如果i是没有遍历过的，那么i入队 27 { 28 q.push(v.to); 29 vis[v.to] = 1; 30 } 31 } 32 } 33 } 34 } 35 int main() 36 { 37 int n,m,a,b,c; 38 node t; 39 cin>>n>>m; 40 for(int i=1;i<=m;i++) 41 { 42 scanf("%d %d %d",&a,&b,&c); 43 t.to = b,t.d = c; 44 g[a].push_back(t); 45 t.to = a,t.d = c; 46 g[b].push_back(t); 47 } 48 spfa(1); 49 cout<<dis[n]; 50 return 0; 51 }