CUBE-189: God of War

#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;
const int N = 1e5;
using pi = pair <int, int>;
using pii = pair <int, pi>;
vector <pi> g[N+10];
int dis[N+10][2];
bool vs[N+10][2];

int main(){

    int n, m;
    scanf("%d%d", &n, &m);

    int s, t;
    scanf("%d%d", &s, &t);

    int sum = 0;

    for(int i=1;i<=m;i++){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        sum += w;
    }

    for(int i=0;i<=n;i++){
        dis[i][0] = dis[i][1] = INF;
        vs[i][0] = vs[i][1] = false;
    }

    priority_queue <pii, vector <pii>, greater <pii>> pq;
    dis[s][0] = 0;
    pq.push({dis[s][0], {s, 0}});

    while(!pq.empty()){
        int d = pq.top().first;
        int u = pq.top().second.first;
        int c = pq.top().second.second;
        pq.pop();
        if(vs[u][c]) continue;
        // printf("u %d d %d c %d \n", u, d, c);
        vs[u][c] = true;
        if(u == t and c == 1) break;
        for(auto vw: g[u]){
            int v = vw.first;
            int w = vw.second;
            if(c == 0){
                if(!vs[v][0] and d + w < dis[v][0]){
                    dis[v][0] = d + w;
                    pq.push({dis[v][0], {v, 0}});
                }
                if(!vs[v][1] and d < dis[v][1]){
                    dis[v][1] = d;
                    pq.push({dis[v][1], {v, 1}});
                }
            }
            else if(c == 1 and !vs[v][1] and d + w < dis[v][1]){
                dis[v][1] = d + w;
                pq.push({dis[v][1], {v, 1}});
            }
        }
    }

    // printf("%d %d\n", sum, dis[t][1]);

    printf("%d", sum - dis[t][1]);

    return 0;
}

/*


4 4
0 4
0 1 1
1 2 1
2 3 1
0 4 1000

1003

7 10
4 5
0 1 2
0 2 3
0 3 1
4 0 10
3 4 8
2 1 5
1 6 2
5 2 2
5 6 4
2 3 7

39

*/