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

旅行 【多源多汇最短路】"/>

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)