【最短路】最短路径树入门

Description

n个城市用m条双向公路连接，使得任意两个城市都能直接或间接地连通。其中城市编号为1..n，公路编号为1..m。
任意个两个城市间的货物运输会选择最短路径，把这n*(n-1)条最短路径的和记为S。现在你来寻找关键公路r，公
路r必须满足：当r堵塞之后，S的值会变大（如果r堵塞后使得城市u和v不可达，则S为无穷大）。

Input

第1行包含两个整数n,m，
接下来的m行，每行用三个整数描述一条公路a,b,len（1<=a,b<=n），
表示城市a和城市b之间的公路长度为len，这些公路依次编号为1..m。
n<=100，1<=m<=3000，1<=len<=10000。

Output

从小到大输出关键公路的编号。

Sample Input

Sample Output

分析

思路比较清晰

我们可以对每个点先建一个最短路径树出来，然后枚举每条边作为删除边，再跑一遍最短路看S是否变大即可。

建议使用Dijkstra + 堆优化

代码

#include<bits/stdc++.h> 
using namespace std;
struct edge {
    int v, w, next;
    int id;
} e[6010];
int head[3010], cnt;

int n, m;
int dis[110], tree[110];
bool vis[110], ans[3010];

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    return x * f;
}

void insert(int u, int v, int w, int id) {
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].id = id;
    e[cnt].next = head[u];
    head[u] = cnt;
}

struct node {
    int f, s;
    node() {}
    node(int ff, int ss) {
 f = ff;
 s = ss;
    }
    bool operator < (const node & x) const {
 return x.s < s;
    }
};

void dijkstra(int u, int del) {
    priority_queue<node> q;
    memset(dis, 0x3f3f3f3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    q.push(node(u, 0));
    dis[u] = 0;
    while (!q.empty()) {
 int f = q.top().f, s = q.top().s;
        q.pop();
 if (vis[f]) continue;
 vis[f] = 1;
 if (s != dis[f]) continue;
 for (int i = head[f]; i; i = e[i].next) {
     if (e[i].id == del) continue;
     int v = e[i].v, w = e[i].w;
     if (dis[v] > dis[f] + w) {
  dis[v] = dis[f] + w;
  q.push(node(v, dis[v]));
  if (!del) tree[v] = e[i].id;
     }
 }
    }
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
 int u = read(), v = read(), w = read();
 insert(u, v, w, i);
 insert(v, u, w, i);
    }
    for (int i = 1; i <= n; i++) {
 dijkstra(i, 0);
 int sum = 0;
 for (int j = 1; j <= n; j++) sum += dis[j];
 for (int j = 1; j <= n; j++) if (tree[j] && !ans[tree[j]]) {
     dijkstra(i, tree[j]);
     int cnt = 0;
     for (int k = 1; k <= n; k++) cnt += dis[k];
     if (cnt > sum) ans[tree[j]] = true;
 }
    }
    for (int i = 1; i <= m; i++) if (ans[i]) {
 printf("%d\n", i);
    }
    return 0;
}