Lightoj1002——Country Roads（最短路變形）

I am going to my home. There are many cities and many bi-directional roads between them. The cities are numbered from 0 to n-1 and each road has a cost. There are m roads. You are given the number of my city t where I belong. Now from each city you have to find the minimum cost to go to my city. The cost is defined by the cost of the maximum road you have used to go to my city.

For example, in the above picture, if we want to go from 0 to 4, then we can choose

1) 0 - 1 - 4 which costs 8, as 8 (1 - 4) is the maximum road we used

2) 0 - 2 - 4 which costs 9, as 9 (0 - 2) is the maximum road we used

3) 0 - 3 - 4 which costs 7, as 7 (3 - 4) is the maximum road we used

So, our result is 7, as we can use 0 - 3 - 4.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a blank line and two integers n (1 ≤ n ≤ 500) and m (0 ≤ m ≤ 16000). The next m lines, each will contain three integers u, v, w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 20000) indicating that there is a road between u and v with cost w. Then there will be a single integer t (0 ≤ t < n). There can be multiple roads between two cities.

Output

For each case, print the case number first. Then for all the cities (from 0 to n-1) you have to print the cost. If there is no such path, print ‘Impossible’.

Sample Input

2

5 6

0 1 5

0 1 4

2 1 3

3 0 7

3 4 6

3 1 8

1

5 4

0 1 5

0 1 4

2 1 3

3 4 7

Output for Sample Input

1

Case 1:

4

3

7

7

Case 2:

4

3

Impossible

Impossible

從u到v點有多條路徑，路徑的花費是權值最長的那段路，而u到v的最短路徑就是花費最小的那個。求給出的點到其他點的所有最短路徑

設dis儲存目前點的最短路，由于題目還是求最短路，是以本質上還是要每次找到個最小的dis，不同的是dis的求法。

另外還要注意有重邊

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cstdio>
#include <set>
#include <cmath>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAXN 25
#define Mod 10001
using namespace std;
int map[][],vis[],dis[],n,m;
void dijkstra(int s)
{
    int i,j,mi,v;
    memset(vis,,sizeof(vis));
    for(i=; i<n; ++i)
    {
        dis[i]=map[s][i];
    }
    dis[s]=;
    vis[s]=;
    for(i=; i<n; ++i)
    {
        mi=INF;
        for(j=; j<n; ++j)
        {
            if(!vis[j]&&dis[j]<mi)
            {
                mi=dis[j];
                v=j;
            }
        }
        vis[v]=;
        for(j=; j<n; ++j)
        {
            if(!vis[j]&&map[v][j]<INF)
            {
                int tmp=max(dis[v],map[v][j]);
                dis[j]=min(dis[j],tmp);
            }
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int cas=; cas<=t; ++cas)
    {
        scanf("%d%d",&n,&m);
        for(int i=; i<n; ++i)
            for(int j=; j<n; ++j)
                map[i][j]=INF;
        while(m--)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            if(map[u][v]>w)
            {
                map[u][v]=w;
                map[v][u]=w;
            }
        }
        int s;
        scanf("%d",&s);
        dijkstra(s);
        printf("Case %d:\n",cas);
        for(int i=; i<n; ++i)
        {
            if(dis[i]<INF)
                printf("%d\n",dis[i]);
            else
                printf("Impossible\n");
        }
    }
    return ;
}