ZOJ3166-Lazy Tourist

朱雀 2021-11-26 13:22 176阅读 0赞

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3166

  1. #include<stdio.h>
  2. #include<string.h>
  3. #define INF 0xfffffff
  4. #define N 102
  5. int map[N][N],hot[N],n,min,c;
  6. void floyd()
  7. {
  8. int i,j,k,t;
  9. for(k=1;k<=n;k++)
  10. for(i=1;i<=n;i++)
  11. for(j=1;j<=n;j++)
  12. if(map[i][j]>map[i][k]+map[k][j]&&map[i][k]!=INF&&map[k][j]!=INF)
  13. map[i][j]=map[i][k]+map[k][j];
  14. for(i=1,t=-1,min=INF;i<=c;i++)
  15. if(map[hot[i]][hot[i]]<min)
  16. min=map[t=hot[i]][hot[i]];
  17. if(t==-1)
  18. printf("I will nerver go to that city!\n");
  19. else
  20. printf("%d\n",t);
  21. }
  22. int main(void)
  23. {
  24. int i,j,m,a,b,d;
  25. while(scanf("%d%d",&n,&c)!=EOF)
  26. {
  27. for(i=1;i<=n;i++)
  28. for(j=1;j<=n;j++)
  29. map[i][j]=INF;
  30. for(i=1;i<=c;i++)
  31. scanf("%d",&hot[i]);
  32. scanf("%d",&m);
  33. for(i=1;i<=m;i++)
  34. {
  35. scanf("%d%d%d",&a,&b,&d);
  36. if(map[a][b]>d)
  37. map[a][b]=d;
  38. }
  39. floyd();
  40. }
  41. return 0;
  42. }

转载于:https://www.cnblogs.com/YogurtShen/archive/2012/08/30/2664232.html

发表评论

表情:
评论列表 (有 0 条评论,176人围观)

还没有评论,来说两句吧...

相关阅读

    相关 ZOJ 3941

    题意:有n(10)段时间,会举行party,每个party有开始时间,结束时间,不同party举行时间可能重复。(时间范围为1~1e9) 我们一共最多可以参加m(1e9)