ZOJ 3396 Conference Call 求經過特定3點的最小生成樹

[cpp] 
//ZOJ 3396 Conference Call 
//題意 求經過特定3點的最小生成樹 
//思路：枚舉任何一點作為支撐點 ，特定的3點要相連必須經過共同的一點 ，求這三點到所枚舉點的最短路和，取最小值即為答案 
#include<iostream> 
#include<stdio.h> 
#include<string.h> 
#include<queue> 
using namespace std; 
 
#define INF 50000000 
#define N 20005 
#define M 505 
int n, m, k; 
 
int sta[N]; 
int head[M], num; 
int dis[4][M]; 
bool vis[M], mark[M]; 
 
struct Edge { 
    int from; 
    int to; 
    int val; 
    int next; 
} edge[N]; 
 
void addedge(int from, int to, int val) { 
    edge[num].from = from; 
    edge[num].to = to; 
    edge[num].val = val; 
    edge[num].next = head[from]; 
    head[from] = num++; 
} 
 
void init() { 
    memset(head, -1, sizeof (head)); 
    num = 0; 
} 
 
void spfa(int s, int index) { 
    memset(vis, 0, sizeof (vis)); 
    for (int i = 1; i <= m; ++i) 
        dis[index][i] = INF; 
    queue<int> Q; 
    Q.push(s); 
    dis[index][s] = 0; 
    vis[s] = 1; 
    while (!Q.empty()) { 
        int p = Q.front(); 
        Q.pop(); 
        vis[p] = 0; 
        for (int i = head[p]; i != -1; i = edge[i].next) { 
            if (dis[index][edge[i].to] > dis[index][p] + edge[i].val) { 
                dis[index][edge[i].to] = dis[index][p] + edge[i].val; 
                if (!vis[edge[i].to]) { 
                    Q.push(edge[i].to); 
                    vis[edge[i].to] = 1; 
                } 
            } 
        } 
    } 
} 
 
int main() { 
    int i, j, ca = 1; 
    int a, b, c; 
    while (scanf("%d %d %d", &n, &m, &k) != EOF) { 
        init(); 
        for (i = 1; i <= n; ++i) 
            scanf("%d", &sta[i]); 
        for (i = 1; i <= k; ++i) { 
            scanf("%d %d %d", &a, &b, &c);        
            addedge(a, b, c); 
            addedge(b, a, c); 
        } 
        int bx; 
        int qua; 
        scanf("%d", &qua); 
        printf("Case #%d\n", ca++); 
        for (i = 1; i <= qua; ++i) { 
            scanf("%d %d %d", &a, &b, &c); 
            spfa(sta[a], 1); 
            spfa(sta[b], 2); 
            spfa(sta[c], 3); 
            int ans = INF; 
            for (j = 1; j <= m; ++j) 
                if (dis[1][j] + dis[2][j] + dis[3][j] < ans){ 
                    ans = dis[1][j] + dis[2][j] + dis[3][j]; 
                    bx = j; 
                } 
            printf("Line %d: ", i); 
           // printf("bx :%d %d %d %d\n",bx,dis[1][bx],dis[2][bx],dis[3][bx]); 
            if (ans == INF) 
                printf("Impossible to connect!\n"); 
            else 
                printf("The minimum cost for this line is %d.\n", ans); 
        } 
    } 
    return 0; 
}