ZOJ 3396 Conference Call 求经过特定3点的最小生成树

//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;
}