题目传送门
题意:求往返最短路的最大值。
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; else d = 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; else f = 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; }