Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 确实水~0ms...dijkstra

Posted by 10152130226 at 2016-07-19 16:19:09 on Problem 1125
```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n,cost[101][101],dis[101],vis[101];
const int inf=0x3f3f3f3f;
int dijkstra(int s)
{
memset(vis,0,sizeof(vis));
int i,j;
for(i=1;i<=n;i++)
{
if(i==s)dis[i]=0;
else dis[i]=cost[s][i];
}
vis[s]=1;
for(i=1;i<=n;i++)
{
int t=inf,k;
for(j=1;j<=n;j++)
{
if(vis[j]==0&&dis[j]<t)
t=dis[j],k=j;
}
if(t==inf)break;
vis[k]=1;
for(j=1;j<=n;j++)
{
if(!vis[j]&&dis[k]+cost[k][j]<dis[j])
dis[j]=dis[k]+cost[k][j];
}
}
int ans=-1;
for(i=1;i<=n;i++)
{
if(i==s)continue;
if(dis[i]>ans)ans=dis[i];
}
return ans;
}
int main()
{
while(scanf("%d",&n)&&n!=0)
{
int i,j,k,con,p,t;
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
cost[i][j]=inf;
for(i=1;i<=n;i++)
{
scanf("%d",&con);
for(j=1;j<=con;j++)
{
scanf("%d%d",&p,&t);
cost[i][p]=t;
}
}
int ans=inf;
for(i=1;i<=n;i++)
{
int res=dijkstra(i);
if(res==-1)
{
ans=-1;break;
}
else if(res<ans)ans=res,k=i;
}
if(ans!=inf)printf("%d %d\n",k,ans);
else printf("disjoint\n");
}
return 0;
}```

Followed by: