首页 > 代码库 > poj1502MPI Maelstrom
poj1502MPI Maelstrom
题目链接:http://poj.org/problem?id=1502
dijkstra。
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<iostream> 5 using namespace std; 6 const int inf=0x3f3f3f3f; 7 int pic[110][110]; 8 int vis[110]; 9 int dis[110]; 10 11 int n; 12 13 void dijkstra() 14 { 15 for(int i=1;i<=n;i++){ 16 dis[i]=inf; 17 vis[i]=0; 18 } 19 dis[1]=0; 20 for(int i=0;i<n;i++) 21 { 22 int x,m=inf; 23 for(int y=1;y<=n;y++) if(!vis[y]&&m>dis[y]) m=dis[x=y]; 24 vis[x]=1; 25 for(int y=1;y<=n;y++) if(!vis[y]&&dis[y]>dis[x]+pic[x][y]) dis[y]=dis[x]+pic[x][y]; 26 } 27 } 28 29 int tran(string s) 30 { 31 int len=s.length(); 32 int d=0; 33 for(int i=0;i<len;i++) 34 d=d*10+(s[i]-‘0‘); 35 return d; 36 } 37 38 int main() 39 { 40 41 int d; 42 string s; 43 while(scanf("%d",&n)!=EOF) 44 { 45 46 for(int i=1;i<=n;i++) 47 for(int j=1;j<=n;j++) 48 pic[i][j]=(i==j?0:inf); 49 for(int i=2;i<=n;i++) 50 for(int j=1;j<i;j++) 51 { 52 cin>>s; 53 if(s=="x") continue; 54 else 55 { 56 d=tran(s); 57 pic[i][j]=pic[j][i]=d; 58 } 59 60 61 } 62 dijkstra(); 63 int ans=-1; 64 for(int i=2;i<=n;i++) 65 ans=max(ans,dis[i]); 66 printf("%d\n",ans); 67 } 68 }
poj1502MPI Maelstrom
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。