Andrew Stankevich's Contest (22)-C.cpp

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 20005;
const int M = 200005;
 
int n , m , pre[N] , mcnt;
struct edge {
    int x , w , next;
}e[M];
int ds[N] , dt[N];
bool f[N];
struct opt {
    int x , w;
    opt(int _x , int _w) {
        x = _x , w = _w;
    }
    bool operator < (const opt& R) const {
        return w > R.w;
    }
};
priority_queue< opt > Q;
 
void Dijkstra(int x , int* d) {
    int i , y , z;
    for (i = 1 ; i <= n ; ++ i)
        d[i] = 0x7fffffff , f[i] = 0;
    d[x] = 0 , Q.push(opt(x , 0));
    while (!Q.empty()) {
        x = Q.top().x , Q.pop();
        if (f[x]) continue; f[x] = 1;
        for (i = pre[x] ; ~i ; i = e[i].next) {
            y = e[i].x , z = e[i].w;
            if (!f[y] && d[y] > d[x] + z) {
                d[y] = d[x] + z;
                Q.push(opt(y , d[y]));
            }
        }
    }
}
 
int dfn[N] , low[N] , ncnt;
vector<int> bridge;
 
void dfs(int x , int fa) {
    dfn[x] = low[x] = ++ ncnt;
    for (int i = pre[x] ; ~i ; i = e[i].next) {
        int y = e[i].x;
        if ((LL)ds[x] + e[i].w + dt[y] != ds[n] && (LL)ds[y] + e[i].w + dt[x] != ds[n])
            continue;
        if (!dfn[y]) {
            dfs(y , i ^ 1);
            low[x] = min(low[x] , low[y]);
            if (low[y] > dfn[x]) {
                bridge.push_back(i >> 1);
            }
        } else if (i != fa && dfn[y] < dfn[x])
            low[x] = min(low[x] , dfn[y]);
    }
}
 
void work() {
    int i , x , y , z;
    memset(pre , -1 , sizeof(pre)), mcnt =0;
    for (i = 0 ; i < m ; ++ i) {
        scanf("%d%d%d" , &x,&y,&z);
        e[mcnt] = (edge) {y , z , pre[x]} , pre[x] = mcnt ++;
        e[mcnt] = (edge) {x , z , pre[y]} , pre[y] = mcnt ++;
    }
    Dijkstra(1 , ds);
    Dijkstra(n , dt);
 
    for (i = 1 ; i <= n ; ++ i)
        if (!dfn[i])
            dfs(i , -1);
    printf("%d\n" , bridge.size());
    sort(bridge.begin() , bridge.end());
    for (i = 0 ; i < bridge.size() ; ++ i) {
        if (i) putchar(' ');
        printf("%d" , bridge[i] + 1);
    } puts("");
}
 
int main()
{
    while (~scanf("%d%d",&n,&m))
        work();
    return 0;
}