Submission #833272

#	Time	Username	Problem	Language	Result	Execution time	Memory
833272		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2041 ms	19696 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>

const int INF = 2147483645;
const int maxN = (int)1e5+5;
const ll LLINF = LLONG_MAX;
//const ll mod = 998244353;
const ll mod = 1000000007;

vector<pair<int, ll>> adj[maxN], adj2[maxN];
vector<ll> d, d2;
vector<int> p, p2;
int n;

void dijkstra(int s) {
    d.assign(n+1, LLINF);
    p.assign(n+1, -1);
    vector<bool> u(n+1, false);

    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++) {
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;
        }

        if (d[v] == LLINF)
            break;

        u[v] = true;
        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
            }
        }
    }
}

void dijkstra2(int s) {
    d2.assign(n+1, LLINF);
    p2.assign(n+1, -1);
    vector<bool> u(n+1, false);

    d2[s] = 0;
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++) {
            if (!u[j] && (v == -1 || d2[j] < d2[v]))
                v = j;
        }

        if (d2[v] == LLINF)
            break;

        u[v] = true;
        for (auto edge : adj2[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d2[v] + len < d2[to]) {
                d2[to] = d2[v] + len;
                p2[to] = v;
            }
        }
    }
}

vector<int> restore_path(int s, int t) {
    vector<int> path;

    for (int v = t; v != s; v = p[v])
        path.push_back(v);
    path.push_back(s);

    reverse(path.begin(), path.end());
    return path;
}

void solv() {
	int m, s, t, u, v, a, b;
	vector<pair<pii, ll>> vec;
	ll c;
	cin>>n>>m;
	cin>>s>>t;
	cin>>u>>v;
	for (int i=0;i<m;i++) {
		cin>>a>>b>>c;
		vec.pb(mp(mp(a, b), c));
		adj[a].pb(mp(b, c));
		adj[b].pb(mp(a, c));
	}
	dijkstra(s);
	vector<int> pth = restore_path(s, t);
	map<int, int> chk;
	int len = pth.size();
	for (int i=0;i<len-1;i++) {
		chk[pth[i]] = pth[i+1];
	}
	for (int i=0;i<m;i++) {
		a = vec[i].first.first; b = vec[i].first.second; c = vec[i].second;
		if (chk[a] == b || chk[b] == a) c = 0;
		adj2[a].pb(mp(b, c));
		adj2[b].pb(mp(a, c));
	}
	dijkstra2(u);
	cout<<d2[v]<<'\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t=1;
//	cin>>t;
	while (t--) solv();
}

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