hdoj 2066 一个人的旅行 【多源多汇最短路】

题目：hdoj 2066 一个人的旅行

方法：缩点 + 最短路

分析：看了大神的一篇博客，讲冗余压缩的，然后就想找一个多源最短路练练手。

这个题目就是典型的多源多汇最短路

方法：把全部的源点压缩成一个点，然后汇点压缩成一个点，然后跑最短路

注意：

1：求最短路的时候邻接表存储有重边不影响结果。

2：此题有重边。

3：要特殊处理源点和汇点是同一个点的情况。为0

AC代码：

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1050;
int mp[N][N];
map<int,int> ma;
struct Node
{
    int to,val;
};
vector<Node> v[N];
void add_Node(int x,int y,int z)
{
    v[x].push_back((Node){y,z});
    v[y].push_back((Node){x,z});
}

int dis[N];
bool ok[N];
void spfa(int s)
{
    queue<int> q;
    q.push(s);
    memset(dis,inf,sizeof(dis));
    dis[s]=0;
    while(!q.empty())
    {
        int tmp=q.front();
        q.pop();
        for(int i=0;i<v[tmp].size();i++)
        {
            if(dis[v[tmp][i].to]>dis[tmp]+v[tmp][i].val)
            {
                dis[v[tmp][i].to]=dis[tmp]+v[tmp][i].val;
                q.push(v[tmp][i].to);
            }
        }
    }
}

void MP_clear(int n)
{
    ma.clear();
    for(int i=0;i<=n;i++)
        v[i].clear();
}
int main()
{
    int t,s,d;
    while(~scanf("%d%d%d",&t,&s,&d))
    {
        memset(mp,inf,sizeof(mp));
        int ma_x=0,ma_y=0;
        for(int i=0;i<t;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            mp[x][y]=min(z,mp[x][y]);
            ma_x=max(ma_x,x);
            ma_y=max(ma_y,y);
        }
        memset(ok,0,sizeof(ok));
        int ss=max(ma_x,ma_y)+2,tt=max(ma_x,ma_y)+1;
        for(int i=0;i<s;i++)
        {
            int x;scanf("%d",&x);
            ma[x]=ss;
            ok[x]=1;
        }
        int ff=0;
        for(int i=0;i<d;i++)
        {
            int x;
            scanf("%d",&x);
            ma[x]=tt;
            if(ok[x] && ff==0)
                ff=1;
        }
        if(ff==1)
        {
            printf("0
");
            continue;
        }
        for(int i=1;i<=ma_x;i++)
        {
            for(int j=1;j<=ma_y;j++)
            {
                if(mp[i][j]!=inf)
                {
                    int xx=i,yy=j;
                    if(ma[i])
                        xx=ma[i];
                    if(ma[j])
                        yy=ma[j];
                    add_Node(xx,yy,mp[i][j]);
                }
            }
        }
        spfa(ss);
        printf("%d
",dis[tt]);
        MP_clear(ss);
    }
    return 0;
}