temp.cpp

#include <bits/stdc++.h>

using namespace std;

#define MAX 505
#define INF 100000000
typedef pair<int, int> PII;
vector<int> adj[MAX];
int n, m, s;
int cost[MAX][MAX];
vector<int> shop;
bool shop_vis[MAX];
int dis[MAX][MAX];

void gen()
{
    for(int i=0; i<MAX; i++) adj[i].clear();
    shop.clear();
    memset(shop_vis, 0, sizeof shop_vis);
    for(int i=0; i<MAX; i++){
        for(int j=0; j<MAX; j++){
            dis[i][j] = INF;
        }
    }
}

int dijkstra(int s, int d)
{
    int dist[MAX];
    bool vis[MAX];
    for(int i=0; i<MAX; i++) dist[i] = INF;
    dist[s] = 0;
    memset(vis, false, sizeof vis);
    priority_queue<PII, vector<PII>, greater<PII> > pq;
    pq.push(make_pair(dist[s], s));

    while(!pq.empty()){
        int u = pq.top().second;
        int initial_cost = pq.top().first;
        pq.pop();
        if(vis[u] == true) continue;
        else vis[u] = true;
        if(u == d) return initial_cost;
        for(int i=0; i<adj[u].size(); i++){
            int v = adj[u][i];
            int u_to_v = cost[u][v];
            if(dist[v] > initial_cost + u_to_v){
                dist[v] = initial_cost + u_to_v;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    return INF;
}

bool bfs(int s)
{
    bool vis[MAX];
    memset(vis, false, sizeof vis);
    vis[s] = true;
    queue<int> Q;
    Q.push(s);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        for(int i=0; i<adj[u].size(); i++){
            int v = adj[u][i];
            if(vis[v] == false){
                vis[v] = true;
                Q.push(v);
            }
        }
    }
    if(vis[n-1] == false) return false;
    for(int i=0; i<shop.size(); i++){
        if(vis[shop[i]] == true) shop_vis[i] = true;
    }
    return true;
}

int main()
{
    freopen("in.txt", "r", stdin);
    int cases;
    scanf("%d", &cases);
    int caseno = 0;
    while(cases--){
        gen();
        scanf("%d %d %d", &n, &m, &s);
        for(int i=0; i<s; i++){
            int x;
            scanf("%d", &x);
            if(x == 0 || x == n-1) continue;
            shop.push_back(x);
        }
        for(int i=1; i<=m; i++){
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
            adj[u].push_back(v);
            cost[u][v] = c;
        }
        if(bfs(0) == false){
            printf("Case %d: Impossible\n", ++caseno);
        }
        else {
            for(int i=0; i<shop.size(); i++){
                if(shop_vis[i]){
                    for(int j=i+1; j<shop.size(); j++){
                        if(shop_vis[j]){
                            dis[shop[i]][shop[j]] = dijkstra(shop[i], shop[j]);
                            dis[shop[j]][shop[i]] = dijkstra(shop[j], shop[i]);
                        }
                    }
                }
            }
            for(int i=0; i<shop.size(); i++){
                if(shop_vis[i] == true){
                    dis[0][shop[i]] = dijkstra(0, shop[i]);
                    dis[shop[i]][0] = dijkstra(shop[i], 0);
                }
                if(shop_vis[i] == true){
                    dis[shop[i]][n-1] = dijkstra(shop[i], n-1);
                    dis[n-1][shop[i]] = dijkstra(n-1, shop[i]);
                }
            }
        }
        for(int i=0; i<MAX; i++){
            for(int j=0; j<MAX; j++){
                if(dis[i][j] != INF) cout << i <<  " " << j << " " << dis[i][j] << endl;
            }
        }
    }
}