洛谷题解 P1339 【[USACO09OCT]热浪Heat Wave】

  • A+
所属分类:代码笔记 信息技术

这是标准的最短路径问题。

无向图!无向图!无向图!

重要的事情说三遍!

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  4. int i,j,k,ss,t,n,m,f[2501][2501],c[2501],x,y,z,minn,maxx=10e8;
  5. bool b[2501];
  6. int main()
  7. {
  8.     cin>>n>>m>>ss>>t;
  9.     for(i=1;i<=n;i++)
  10.     {
  11.         for(j=1;j<=n;j++)
  12.         {
  13.             f[i][j]=10e7;               //邻接矩阵初始化。
  14.         }
  15.     }
  16.     for(i=1;i<=m;i++)
  17.     {
  18.         cin>>x>>y>>z;
  19.         f[x][y]=z;
  20.         f[y][x]=z;
  21.     }                                  //数据读入邻接矩阵。注意无向图!
  22.       //然后就是标准的Dijkstra最短路径算法了……
  23.     for(i=1;i<=n;i++)
  24.     {
  25.         c[i]=f[ss][i];
  26.     }
  27.     memset(b,false,sizeof(b));
  28.     b[ss]=true;
  29.     c[ss]=0;
  30.     for(i=1;i<=n-1;i++)
  31.     {
  32.         minn=maxx;
  33.         k=0;
  34.         for(j=1;j<=n;j++)
  35.         {
  36.             if((!b[j])&&(c[j]<minn)){
  37.                 minn=c[j];
  38.                 k=j;
  39.             }
  40.         }
  41.         if(k==0) break;
  42.         b[k]=true;
  43.         for(j=1;j<=n;j++)
  44.         {
  45.             if(c[k]+f[k][j]<c[j]) c[j]=c[k]+f[k][j];
  46.         }
  47.     }
  48.     cout<<c[t];       //输出最小费用
  49.     return 0;
  50. }
xcc

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: