POJ - 3268 Silver Cow Party （往返最短路，Floyd，Dijkstra 2次优化）

本文主要是介绍POJ - 3268 Silver Cow Party （往返最短路，Floyd，Dijkstra 2次优化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目传送门

题意：求往返最短路的最大值。

1、先想到Floyd结果超时了。

2、先用1次Dijkstra求出各点到X的距离，然后再用N-1次算出X到各点的距离。 485ms AC。

3、先用1次Dijkstra算各点到X的距离，然后用相反的邻接表的Dijkstra算出点X到各点的距。 0ms AC了！

直接Floyd：TLE

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int N, M, X;
const int MAXN = 1001, MAXM = 100001, INF = 0x3f3f3f3f;
//struct Edge
//{
//	int u, v, w;
//}e[MAXM];int d[MAXN][MAXN];void Floyd()
{for(int k = 1; k <= N; k++)for(int i = 1; i <= N; i++)for(int j = 1; j <= N; j++)if(d[i][k]+d[k][j] < d[i][j])d[i][j] = d[i][k]+d[k][j];
}int main()
{scanf("%d%d%d", &N, &M, &X);memset(d, 0x3f, sizeof(d));for(int i = 0; i < M; i++){//scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);int u, v, w;scanf("%d%d%d", &u, &v, &w);d[u][v] = w;}Floyd();int Max = 0;for(int i = 1; i <= N; i++){int t = 0;if(i!=X)t = d[i][X] + d[X][i];if(t > Max)Max = t;}printf("%d\n", Max);return 0;
}

1 + N-1次Dijkstra ：485ms

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int N, M, X;
const int MAXN = 1001, MAXM = 100001, INF = 0x3f3f3f3f;
struct Edge
{int u, v, w;
}edge[MAXM], edge1[MAXM];typedef pair <int, int> P;
priority_queue<P, vector<P>, greater<P> > que;
int first[MAXN], nexte[MAXM];
int dis[MAXN], dis1[MAXN];
void Dijkstra(int s, int mod)
{int *f, *n, *d;Edge *e;f = first, n = nexte, e = edge;if(mod == 0)				//正向求n-1次到x的距离d = dis;elsed = dis1;	//反向求x到个点的距离memset(d, 0x3f, sizeof(dis));d[s] = 0;que.push(make_pair(d[s], s));while(que.size()){P u = que.top(); que.pop();int x = u.second;		//起点if(u.first != d[x])		//计算过了，跳过continue;for(int i = f[x]; i != -1; i = n[i])		//松弛邻边if(d[x]+e[i].w < d[e[i].v]){d[e[i].v] = d[x] + e[i].w;que.push(make_pair(d[e[i].v], e[i].v));}}
}int main()
{//freopen("in.txt", "r", stdin);scanf("%d%d%d", &N, &M, &X);//memset(d, 0x3f, sizeof(d));memset(first, -1, sizeof(first));for(int i = 0; i < M; i++){scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);nexte[i] = first[edge[i].u];first[edge[i].u] = i;}Dijkstra(X, 1);int Max = 0;for(int i = 1; i <= N; i++)if(i!=X){Dijkstra(i, 0);dis1[i] += dis[X];Max = max(dis1[i], Max);}printf("%d\n", Max);return 0;
}

2次Dijkstra：0ms

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int N, M, X;
const int MAXN = 1001, MAXM = 100001, INF = 0x3f3f3f3f;
struct Edge
{int u, v, w;
}edge[MAXM], edge1[MAXM];typedef pair <int, int> P;
priority_queue<P, vector<P>, greater<P> > que;
int first[MAXN], nexte[MAXM], first1[MAXN], nexte1[MAXM];
int dis[MAXN], dis1[MAXN];
void Dijkstra(int s, int mod)
{int *f, *n, *d;Edge *e;if(mod == 0)				//正向求n-1次到x的距离f = first, n = nexte, d = dis, e = edge;elsef = first1, n = nexte1, d = dis1, e = edge1;	//反向求x到个点的距离memset(d, 0x3f, sizeof(dis));d[s] = 0;que.push(make_pair(d[s], s));while(que.size()){P u = que.top(); que.pop();int x = u.second;		//起点if(u.first != d[x])		//计算过了，跳过continue;for(int i = f[x]; i != -1; i = n[i])		//松弛邻边if(d[x]+e[i].w < d[e[i].v]){d[e[i].v] = d[x] + e[i].w;que.push(make_pair(d[e[i].v], e[i].v));}}
}int main()
{//freopen("in.txt", "r", stdin);scanf("%d%d%d", &N, &M, &X);memset(first, -1, sizeof(first));memset(first1, -1, sizeof(first1));for(int i = 0; i < M; i++){scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);edge1[i].v = edge[i].u, edge1[i].u = edge[i].v, edge1[i].w = edge[i].w;nexte[i] = first[edge[i].u];first[edge[i].u] = i;//反方向nexte1[i] = first1[edge1[i].u];first1[edge1[i].u] = i;}Dijkstra(X, 1);int Max = 0;//for(int i = 1; i <= N; i++)//	if(i!=X)//	{//		Dijkstra(i, 0);//		dis1[i] += dis[X];//		Max = max(dis1[i], Max);//	}Dijkstra(X, 0);for(int i = 1; i <= N; i++)if(i!=X)Max = max(dis1[i]+dis[i], Max);printf("%d\n", Max);return 0;
}

这篇关于POJ - 3268 Silver Cow Party （往返最短路，Floyd，Dijkstra 2次优化）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---