ZOJ3166-Lazy Tourist

朱雀 2021-11-26 13:22 184阅读 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 条评论，184人围观）

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

相关阅读

    相关 ZOJ 3941

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

    淩亂°似流年淩亂°似流年/ 0 赞/ 295 阅读