简单最短路
题意:在n个人中散布谣言,选择一个人把谣言告诉他,他再继续告诉别人,知道所有人都知道
求选择起始的人,和最短时间
求出每个人为起始人传播谣言所用的最短时间
#include<stdio.h> #include<string.h> #define inf 0x3fffffff int map[110][110],n,m,vis[110],dis[110]; int dijkstra(int st) { int i,j,k,max=-1,min; memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) dis[i]=inf; dis[st]=0; for(i=1;i<=n;i++) { min=inf;k=-1; for(j=1;j<=n;j++) { if(!vis[j]&&min>dis[j]) min=dis[j],k=j; } if(k==-1) return -1; vis[k]=1; for(j=1;j<=n;j++) if(!vis[j]&&dis[j]>dis[k]+map[k][j]) { dis[j]=dis[k]+map[k][j]; if(max<dis[j]) max=dis[j]; } } return max; } int main() { int i,j,k,w,sum; while(scanf("%d",&n)!=-1&&n) { for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) map[i][j]=map[j][i]=inf; for(i=1;i<=n;i++) { scanf("%d",&k); while(k--) { scanf("%d%d",&j,&w); map[i][j]=w; } } int min=inf; for(i=1;i<=n;i++) { sum=dijkstra(i); if(min>sum&&sum!=-1) {k=i;min=sum;} } printf("%d %d\n",k,min); } return 0; }