首页 > 代码库 > hdu 1874
hdu 1874
1 #include <bits/stdc++.h> 2 #define inf 0x3f3f3f3f 3 4 using namespace std; 5 6 int N, M; 7 int map1[205][205]; 8 int d[205]; 9 int vis[205]; 10 void dij(int start) 11 { 12 for(int i=0; i<N; i++) 13 { 14 d[i]=(i==start?0:inf); 15 } 16 for(int i=0; i<N; i++) 17 { 18 int ij=inf, u; 19 for(int j=0; j<N; j++) 20 { 21 if(!vis[j]&&d[j]<=ij) 22 { 23 ij=d[j]; 24 u=j; 25 } 26 } 27 vis[u]=1; 28 if(ij==inf) break; 29 for(int v=0; v<N; v++) 30 { 31 if(!vis[v]) 32 d[v]=min(d[v], map1[u][v]+d[u]); 33 } 34 } 35 } 36 int main() 37 { 38 while(scanf("%d %d", &N, &M)!=EOF) 39 { 40 memset(vis, 0, sizeof(vis)); 41 for(int i=0; i<N; i++) 42 { 43 for(int j=0; j<N; j++) 44 { 45 map1[i][j]=(i==j?0:inf); 46 } 47 } 48 for(int i=0; i<M; i++) 49 { 50 int x, y, z; 51 scanf("%d%d%d", &x, &y, &z); 52 if(z<map1[x][y]) 53 { 54 map1[x][y]=map1[y][x]=z; 55 } 56 } 57 int s, t; 58 scanf("%d%d", &s, &t); 59 dij(s); 60 if(d[t]==inf) printf("-1\n"); 61 else cout <<d[t] <<endl; 62 } 63 64 return 0; 65 }
hdu 1874
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。