[POJ1797] Heavy Transportation（最大生成树 || 最短路变形）

传送门

1.最大生成树

　　可以求出最大生成树，其中权值最小的边即为答案。

2.最短路

　　只需改变spfa里面的松弛操作就可以求出答案。

——代码

 #include <queue>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int MAXN = ;

 int T, n, m, cnt;

 int head[MAXN], next[MAXN * MAXN], to[MAXN * MAXN], val[MAXN * MAXN], dis[MAXN];

 bool vis[MAXN];

 queue <int> q;

 inline void add(int x, int y, int z)

 {

     to[cnt] = y;

     val[cnt] = z;

     next[cnt] = head[x];

     head[x] = cnt++;

 }

 inline void spfa(int u)

 {

     int i, v;

     memset(dis, , sizeof(dis));

     memset(vis, , sizeof(vis));

     while(!q.empty()) q.pop();

     q.push(u);

     vis[u] = ;

     dis[u] = 0x3f3f3f3f;

     while(!q.empty())

     {

         u = q.front();

         q.pop();

         vis[u] = ;

         for(i = head[u]; i != -; i = next[i])

         {

             v = to[i];

             if(min(dis[u], val[i]) > dis[v])

             {

                 dis[v] = min(dis[u], val[i]);

                 if(!vis[v])

                 {

                     q.push(v);

                     vis[v] = ;

                 }

             }

         }

     }

 }

 int main()

 {

     int i, j, x, y ,z;

     scanf("%d", &T);

     for(i = ; i <= T; i++)

     {

         scanf("%d %d", &n, &m);

         cnt = ;

         memset(head, -, sizeof(head));

         for(j = ; j <= m; j++)

         {

             scanf("%d %d %d", &x, &y, &z);

             add(x, y, z);

             add(y, x, z);

         }

         spfa();

         printf("Scenario #%d:\n", i);

         printf("%d\n\n", dis[n]);

     }

     return ;

 }