HDU2066 一個人的旅行

最短路

題目傳送門

一道比較複雜（看上去）的最短路。有多個起點，多個終點，還有重邊。

對于多個起點和多個終點，分别建一個超級源(s)和超級彙(t)，然後在s和起點間建一條權值為1的邊（多少都無所謂啦）（指向起點），t也是如此（指向t）。問題就變成從s到t的最短路（記得把答案減2）。

重邊什麼的做一個鄰接表直接跑（深深感受到了鄰接表的強大）。

貼個代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct edge{
    int next;
    int to;
    int dis;
};
int n,m,u,v,d,k,c;
int h[],dis[],s,t;
edge a[];
bool f[];
int spfa(){
    memset(dis,,sizeof(dis));
    int b[];
    int r=,w=;
    dis[]=; b[]=; f[]=true;
    while (r<w){
        int x=b[++r];
        f[x]=false;
        for (int i=h[x];i;i=a[i].next)
            if (dis[a[i].to]>dis[x]+a[i].dis){
                dis[a[i].to]=dis[x]+a[i].dis;
                if (!f[a[i].to]){
                    b[++w]=a[i].to;
                    f[a[i].to]=true;
                }
            }
    }
    return dis[];
}
void read(int x,int y,int z){
    k++;
    a[k].next=h[x];
    a[k].to=y;
    a[k].dis=z;
    h[x]=k;
}
int main(){
    while (scanf("%d%d%d",&m,&n,&c)!=EOF){
        memset(f,false,sizeof(f));
        memset(h,,sizeof(h));
        k=;
        for (int i=;i<=m;i++){
            scanf("%d%d%d",&u,&v,&d);
            read(u,v,d);
            read(v,u,d);
        }
        for (int i=;i<=n;i++){
            scanf("%d",&s);
            read(,s,);
        }
        for (int i=;i<=c;i++){
            scanf("%d",&t);
            read(t,,);
        }
        printf("%d\n",spfa()-);
    }
    return ;
}