欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

kuangbin最短路专题Silver Cow Party (POJ - 3268)

程序员文章站 2022-07-13 11:29:13
...

kuangbin最短路专题4

传送门

题面kuangbin最短路专题Silver Cow Party (POJ - 3268)

思路

老方法dijkstra。单向图。正向反向的图都建一遍。正向的图跑奶牛去参加聚会的最短路,反向的图跑回家的最短路。不建反向图就得跑n遍dij

代码

#include <bits/stdc++.h>//poj不能用万能头,这里是为了看起来简洁点
typedef long long ll;
#define mP make_pair
#define pii pair<int, int> 
using namespace std;

int n, m, k;
bool vis[1005];
int dis[1005][1005];
struct lxm
{
	int to, cost, nxt;
}edge[100005], edge1[1000005];
int head[1005], cnt = 0, cnt1 = 0, head1[1005];
int ans[1005], ans1[1005];//这三行另开一组数组存反向边
void addedge(int u, int v, int c)
{
	edge[++cnt].to = v;
	edge[cnt].cost = c;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
	edge1[++cnt1].to = u;
	edge1[cnt1].cost = c;
	edge1[cnt1].nxt = head1[v];
	head1[v] = cnt1;
}
void dij(int s)//老dij了
{
	ans[s] = ans1[s] = 0;
	priority_queue<pii, vector<pii>, greater<pii> >Q;
	Q.push(mP(0, s));
	while (Q.size())
	{
		pii tmp = Q.top(); Q.pop();
		int u = tmp.second;
		if (vis[u])continue;
		vis[u] = 1;
		for (int i = head[u]; i; i = edge[i].nxt)
		{
			if (ans[edge[i].to] > ans[u] + edge[i].cost)
			{
				ans[edge[i].to] = ans[u] + edge[i].cost;
				Q.push(mP(ans[edge[i].to], edge[i].to));
			}
		}
	}
	memset(vis, 0, sizeof(vis));//记得这一步
	Q.push(mP(0, s));//两次dij完全一样,只是改个数组名
	while (Q.size())
	{
		pii tmp = Q.top(); Q.pop();
		int u = tmp.second;
		if (vis[u])continue;
		vis[u] = 1;
		for (int i = head1[u]; i; i = edge1[i].nxt)
		{
			if (ans1[edge1[i].to] > ans1[u] + edge1[i].cost)
			{
				ans1[edge1[i].to] = ans1[u] + edge1[i].cost;
				Q.push(mP(ans1[edge1[i].to], edge1[i].to));
			}
		}
	}
}
void solve()
{
	memset(vis, 0, sizeof(vis));
	memset(ans, 0x3f3f3f3f, sizeof(ans));
	memset(ans1, 0x3f3f3f3f, sizeof(ans1));
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		cin >> x >> y >> c;
		addedge(x, y, c);
	}
	dij(k);
	int mans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (i == k)continue;
//这里一定要continue,因为ans[k]+ans1[k]==0,要是不跳,mans又回到0了
		mans = max(mans, ans[i] + ans1[i]);
	}
	cout << mans << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	//int numoftest; cin >> numoftest;
	//for (register int siven = 1; siven <= numoftest; ++siven)

	solve();
	return 0;
}

/*

*/

相关标签: kuangbin专题