AcWing 1132. 农场派对（最短路反向建边）

题目链接

https://www.acwing.com/problem/content/1134/

http://poj.org/problem?id=3268

思路

我们想求所有点到x的距离以及x到所有点的距离，对于后者，我们直接对x跑一个最短路 O ( N 2 l o g n ) O(N^2log_n) O(N2logn​)范围内的算法都可以那么对于前者呢，如果正面去想我们肯定会想到直接跑N次最短路就好了，但是我们其实可以将有向边反建，然后再对x跑一次最短路，为什么这样就能算出来呢，因为你想我们从一个点 i i i到 x x x的边如果反着建的话我们从 x x x到 i i i的路径效果不就和 i i i到 x x x正着一样吗，所以我们反向建边再跑一次最短路就好啦

代码

#include
using namespace std;
#define PII pair
#define INF 0x3f3f3f3f
const int N = 1e3+10;
int dis[N][2],n,x,m;
struct Node{
	int v,w;
};
vector E[2][N];
bool vis[N];


void DJ(int s,int loc){
	memset(vis,0,sizeof vis);
	
	priority_queue que;
	que.push({0,s});
	dis[s][loc] = 0;
	while(!que.empty()){
		int t = que.top().second;
		que.pop();
		if(vis[t]) continue;
		vis[t] = true;
		
		for(int i  = 0, l = E[loc][t].size();i  dis[t][loc] + w){
				dis[j][loc] = dis[t][loc] + w;
				que.push({dis[j][loc],j});
			}
		}
	}
	
}


int main()
{
	memset(dis,0x3f,sizeof dis);
	cin>>n>>m>>x;
	int u,v,w;
	for(int i = 1;i >u>>v>>w;
		E[0][u].push_back({v,w});//正向建图
		E[1][v].push_back({u,w});//反向建图
	}
	DJ(x,0);
//	for(int i = 1;i