ZOJ 3396

斯坦那树有一个结论：n个点的斯坦那树至少会经过n-2个中间节点，这里n=3，所以至少会经过一个中间节点，求出这三个点的单源最短路后枚举中间节点即可。

要注意虽然枚举有一些点时，并不是简单的三个dist相加，但最小的一定是三个相加

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define N 510
#define inf 6000000
using namespace std;
struct Edge{
    int v,w,next;
}edge[12000*2];
int val[11000],head[N],cnt,dis[N][N];
bool vis[N],ok[10100];
void init(int n){
    int i,j;
    memset(head,-1,sizeof(head));
    memset(ok,0,sizeof(ok));
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            dis[i][j]=inf;
    cnt=0;
}
void addedge(int u,int v,int w){
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].v=u;
    edge[cnt].w=w;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
void spfa(int s){
    int i;
    queue<int>q;
    dis[s][s]=0;
    memset(vis,0,sizeof(vis));
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].v;
            if(dis[s][v]>dis[s][u]+edge[i].w){
                dis[s][v]=dis[s][u]+edge[i].w;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    int n,m,l,i,j,q;
    int u,v,w;
    int x,y,z;
    int ans;
    int cas=0;
    while(scanf("%d %d %d",&n,&m,&l)==3){
        init(m);
        for(i=1;i<=n;i++)
            scanf("%d",&val[i]);
        for(i=1;i<=l;i++){
            scanf("%d %d %d",&u,&v,&w);
            addedge(u,v,w);
        }
        scanf("%d",&q);
        printf("Case #%d\n",++cas);
        for(j=1;j<=q;j++){
            scanf("%d %d %d",&x,&y,&z);
            if(ok[val[x]]==0){
                spfa(val[x]);
                ok[val[x]]=1;
            }
            if(ok[val[y]]==0){
                spfa(val[y]);
                ok[val[y]]=1;
            }
            if(ok[val[z]]==0){
                spfa(val[z]);
                ok[val[z]]=1;
            }
            ans=inf*3;
            for(i=1;i<=m;i++)
                if(dis[val[x]][i]!=inf && dis[val[y]][i]!=inf && dis[val[z]][i]!=inf)
                    ans=min(ans,dis[val[x]][i]+dis[val[y]][i]+dis[val[z]][i]);
            if(ans==inf*3)
                printf("Line %d: Impossible to connect!\n",j);
            else
                printf("Line %d: The minimum cost for this line is %d.\n",j,ans);
        }
    }
}