Submission #1104522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104522		hiensumi	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	152 ms	20412 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define fod(i,a,b) for(int i((int) (a)), _b(b); i <= _b; i++)
#define fok(i,a,b) for(int i((int) (a)), _b(b); i >= _b; i--)
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ve vector
#define vi ve<int>
#define vll ve<ll>
#define el '\n'
#define mask(i) (1LL<<(i))
#define BIT(msk,i) (msk>>(i)&1LL)
template<class T> bool mini(T &a, T b){ return (a > (b) ? a = (b), 1 : 0); }
template<class T> bool maxi(T &a, T b){ return (a < (b) ? a = (b), 1 : 0); }
const int base = mask(20) + 5;
#define name "commuter_pass"

const int N = 1e5;

int n, m;

int S, T;
int U, V;

struct Node{
    int v, w, id;
};

ve <ve<Node>> g;

bool fri[2 * N + 5];

ll dis[N + 5];
pii trace[N + 5];

inline ll djikstra(int s, int t){
    fod(i,1,n) dis[i] = 1e18;
    dis[s] = 0;

    priority_queue <pair<ll,int>> pq;

    pq.push(mp(0, s));

    while(!pq.empty()){
        ll val;
        int u;
        tie(val, u) = pq.top(); pq.pop();

        if(-val != dis[u]) continue;

        for(Node who : g[u]){
            int v = who.v, w = who.w, id = who.id;

            if(fri[id]) w = 0;

            if(mini(dis[v], dis[u] + w)){
                pq.push(mp(-dis[v], v));
                trace[v] = mp(u, id);
            }
        }
    }

    ll res = dis[t];

    while(t != s and t != 0){
        fri[trace[t].se] = 1;
        t = trace[t].fi;
    }

    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    if(fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    cin >> n >> m;

    cin >> S >> T;
    cin >> U >> V;

    g.resize(n + 1);
    fod(i,1,m){
        int u, v, w; cin >> u >> v >> w;
        g[u].pb(Node{v, w, i});
        g[v].pb(Node{u, w, i});
    }

    djikstra(S, T);

    cout << djikstra(U, V);

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45