C - Heavy Transportation-白红宇

C - Heavy Transportation

阅读量：5153 次

发布时间：2019-06-13

本文共 1443 字，大约阅读时间需要 4 分钟。

这个题和B的类型差不多，都算是dijkstra的变形，但是这个更难想一点。让dis[i]存储1到各点最短路径的最大值。之所以可以用dijkstra，是因为对于每一次只要选当前最大的dis[v]，那么这个dis一定是到v的最短路径的最大值。因为如果这条边不是的话，那么就有dis[v]=min(dis[u],g[u][v]),但是因为dis[v]是当前dis中的最大值，所以dis[v]>dis[u],如果g[u][v]>dis[v],那么dis[v]=dis[v],否则dis[v]=g[u][v]<dis[v],因此dis[v]一定是所求解，这样就可以通过松弛策略不断的推进。策略是和dijkstra求最短路一样的，表示的意义不太一样。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
         5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 using namespace std;13 const double Pi=3.14159265358979323846;14 typedef long long ll;15 const int MAXN=1000+5;16 const int dx[5]={ 0,0,0,1,-1};17 const int dy[5]={ 1,-1,0,0,0};18 const int INF = 0x3f3f3f3f;19 const int NINF = 0xc0c0c0c0;20 const ll mod=1e9+7;21 int G[MAXN][MAXN];22 int dis[MAXN],pre[MAXN];23 void dijkstra(int n)24 {25 for(int i=1;i<=n;i++) 26 {27 if(G[1][i]!=0) dis[i]=G[1][i];28 }29 dis[1]=0;30 int U[MAXN];31 for(int i=1;i<=n;i++) U[i]=0;32 U[1]=1;33 for(int i=1;i<=n-1;i++)34 {35 int minn=0;int k;36 for(int j=1;j<=n;j++)37 {38 if(U[j]) continue;39 if(minn
                
                 >t;int cnt=1;57 while(t--)58 {59 memset(G,0,sizeof(G));60 memset(dis,0,sizeof(dis));61 int n,m;cin>>n>>m;62 while(m--)63 {64 int a,b,c;cin>>a>>b>>c;65 G[a][b]=c;G[b][a]=c;66 }67 dijkstra(n);68 printf("Scenario #%d:\n%d\n\n",cnt++,dis[n]); 69 }70 return 0; 71 }

转载于:https://www.cnblogs.com/Msmw/p/10811136.html

你可能感兴趣的文章