首页 > 代码库 > POJ 2387 Til the Cows Come Home
POJ 2387 Til the Cows Come Home
题目描述
给定的n个点中有m条边,求从1到n之间的最短距离。
题解
裸的,bellman-Ford 或者spfa就好了。好久没打最短路了随手打了一下。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 const int INF = 1e9; 9 const int M = 1000 + 10; 10 int to[M * 2], nxt[M * 2], w[M * 2]; 11 int head[M * 2], tot; 12 int dis[M * 2]; 13 int m, n; 14 void add(int u,int v,int c) 15 { 16 w[tot] = c; 17 to[tot] = v; 18 nxt[tot] = head[u]; 19 head[u] = tot++; 20 } 21 void spfa(int s) 22 { 23 bool vis[M]; 24 memset(vis, false, sizeof(vis)); 25 queue<int> q; 26 for(int i=0; i<=n; i++) 27 dis[i]=INF; 28 q.push(s); 29 dis[s] = 0; 30 vis[s] = true; 31 while(!q.empty()) 32 { 33 int u = q.front(); 34 q.pop(); 35 for(int i = head[u]; i != -1; i = nxt[i]) 36 { 37 int v = to[i]; 38 if(dis[v] > dis[u] + w[i]) 39 { 40 dis[v] = dis[u] + w[i]; 41 if(!vis[v]) 42 { 43 vis[s] = true; 44 q.push(v); 45 } 46 } 47 } 48 } 49 } 50 int main() 51 { 52 scanf("%d%d", &m, &n); 53 memset(head,-1,sizeof(head)); 54 while(m--) 55 { 56 int u,v,c; 57 scanf("%d%d%d",&u,&v,&c); 58 add(u,v,c); 59 add(v,u,c); 60 } 61 spfa(1); 62 printf("%d\n",dis[n]); 63 return 0; 64 }
POJ 2387 Til the Cows Come Home
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。