次短路,枚举删掉最短路上每条边,这题是取最大值即可。
SPFA比较快。优先队列犯了个比较2的错误。。。用pair没写比较函数。
SPFA
#include <set> #include <map> #include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <string> #include <algorithm> #define MID(x,y) ( ( x + y ) >> 1 ) #define L(x) ( x << 1 ) #define R(x) ( x << 1 | 1 ) #define FOR(i,s,t) for(int i=s; i<t; i++) #define BUG puts("here!!!") using namespace std; const int MAX = 1010; const int MAX_NODE = 100010; typedef struct NODE{ int to,len,id; bool flag; NODE *next; }NODE; NODE *p[MAX],node[MAX_NODE]; int cou; void Add(int from,int to,int len) { node[cou].next = p[from]; node[cou].to = to; node[cou].len = len; node[cou].id = cou; node[cou].flag = true; p[from] = &node[cou++]; } queue<int> q; int Dijkstra_List_first(int from,int to,int n) { while( !q.empty() ) q.pop(); int dis[MAX]; int pre[MAX], id[MAX]; bool used[MAX]; memset(used,false,sizeof(used)); for(int i=1; i<=n; i++) dis[i] = INT_MAX, pre[i] = i; dis[from] = 0; used[from] = true; int now = from; for(int i=1; i<=n; i++) { NODE *head = p[now]; while( head != NULL ) { int len = head->len; int v = head->to; if( dis[v] > dis[now] + len ) { dis[v] = dis[now] + len; pre[v] = now; id[v] = head->id; } head = head->next; } int min = INT_MAX; for(int k=1; k<=n; k++) if( !used[k] && dis[k] < min ) min = dis[now = k]; if( min == INT_MAX ) break; used[now] = true; } if( dis[to] == INT_MAX ) return dis[to]; int f = to; while( f != from ) { q.push(id[f]); f = pre[f]; } return dis[to]; } int SPFA_List(int from,int to,int n) { queue<int> q; while( !q.empty() ) q.pop(); int dis[MAX]; bool inq[MAX]; for(int i=1; i<=n; i++) dis[i] = INT_MAX; memset(inq,false,sizeof(inq)); dis[from] = 0; q.push(from); inq[from] = 1; while( !q.empty() ) { int now = q.front(); q.pop(); inq[now] = false; NODE *head = p[now]; while( head != NULL ) { int v = head->to; int len = head->len; if( dis[v] > dis[now] + len && head->flag ) { dis[v] = dis[now] + len; if( !inq[v] ) { inq[v] = true; q.push(v); } } head = head->next; } } return dis[to]; } int solve(int n) { int ans = Dijkstra_List_first(1, n, n); if( ans == INT_MAX ) return -1; ans = 0; while( !q.empty() ) { int k = q.front(); q.pop(); node[k].flag = false; ans = max(ans, SPFA_List(1, n, n)); node[k].flag = true; } if( ans == INT_MAX ) return -1; return ans; } int main() { int ncases, n, m, u, v, len; scanf("%d", &ncases); while( ncases-- ) { scanf("%d%d", &n, &m); cou = 0; memset(p, 0, sizeof(p)); while( m-- ) { scanf("%d%d%d", &u, &v, &len); Add(u, v, len); Add(v, u, len); } int ans = solve(n); printf("%d\n", ans); } return 0; }
优先队列
#include <set> #include <map> #include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <string> #include <algorithm> #define MID(x,y) ( ( x + y ) >> 1 ) #define L(x) ( x << 1 ) #define R(x) ( x << 1 | 1 ) #define FOR(i,s,t) for(int i=s; i<t; i++) #define BUG puts("here!!!") using namespace std; const int MAX = 1010; const int MAX_NODE = 100010; typedef struct NODE{ int to,len,id; bool flag; NODE *next; }NODE; NODE *p[MAX],node[MAX_NODE]; int cou; void Add(int from,int to,int len) { node[cou].next = p[from]; node[cou].to = to; node[cou].len = len; node[cou].id = cou; node[cou].flag = true; p[from] = &node[cou++]; } queue<int> q; int Dijkstra_List_first(int from,int to,int n) { while( !q.empty() ) q.pop(); int dis[MAX]; int pre[MAX], id[MAX]; bool used[MAX]; memset(used,false,sizeof(used)); for(int i=1; i<=n; i++) dis[i] = INT_MAX, pre[i] = i; dis[from] = 0; used[from] = true; int now = from; for(int i=1; i<=n; i++) { NODE *head = p[now]; while( head != NULL ) { int len = head->len; int v = head->to; if( dis[v] > dis[now] + len ) { dis[v] = dis[now] + len; pre[v] = now; id[v] = head->id; } head = head->next; } int min = INT_MAX; for(int k=1; k<=n; k++) if( !used[k] && dis[k] < min ) min = dis[now = k]; if( min == INT_MAX ) break; used[now] = true; } if( dis[to] == INT_MAX ) return dis[to]; int f = to; while( f != from ) { q.push(id[f]); f = pre[f]; } return dis[to]; } typedef pair<int,int> pii; int Dijkstra_List_priority(int from,int to,int n) // 出发点,终止点,总节点 { priority_queue<pii,vector<pii>,greater<pii> > q; int dis[MAX]; bool used[MAX]; memset(used,false,sizeof(used)); for(int i=1; i<=n; i++) dis[i] = INT_MAX; dis[from] = 0; q.push(make_pair(0, from)); while( !q.empty() ) { int now = q.top().second; q.pop(); if( used[now] ) continue; used[now] = true; NODE *head = p[now]; while( head != NULL ) { int v = head->to; int len = head->len; if( dis[v] > dis[now] + len && head->flag ) { dis[v] = dis[now] + len; q.push(make_pair(dis[v], v)); } head = head->next; } } return dis[to]; } int solve(int n) { int ans = Dijkstra_List_first(1, n, n); if( ans == INT_MAX ) return -1; ans = 0; while( !q.empty() ) { int k = q.front(); q.pop(); node[k].flag = false; ans = max(ans, Dijkstra_List_priority(1, n, n)); node[k].flag = true; } if( ans == INT_MAX ) return -1; return ans; } int main() { int ncases, n, m, u, v, len; scanf("%d", &ncases); while( ncases-- ) { scanf("%d%d", &n, &m); cou = 0; memset(p, 0, sizeof(p)); while( m-- ) { scanf("%d%d%d", &u, &v, &len); Add(u, v, len); Add(v, u, len); } int ans = solve(n); printf("%d\n", ans); } return 0; }