제출 #1167731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167731		diana	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2098 ms	75832 KiB

commuter_pass

#include <bits/stdc++.h>
#pragma GCC oprimize("O3, unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define edge pair<ll, int>
#define c first
#define vi second
using namespace std;

typedef long long ll;

const int N = 1e5+5;
const ll M = 1e18;
int n, m, s, t, u, v;
vector<edge> graf[N];

class vertex
{
private:
    int v;
    vector<ll> dist;
    bool dw;
    void dijkstra()
    {
        if(dw)
            return;
        dist.assign(n, M);
        priority_queue<edge, vector<edge>, greater<edge>> pq;
        bool vis[n] = {};
        pq.push({0, v});
        dist[v] = 0;
        while(!pq.empty())
        {
            edge t = pq.top(); pq.pop();
            if(vis[t.vi])
                continue;
            vis[t.vi] = 1;
            for(auto x: graf[t.vi])
            {
                if(t.c + x.c < dist[x.vi])
                {
                    pq.push({t.c + x.c, x.vi});
                    dist[x.vi] = t.c + x.c;
                }
            }
        }
    }
public:
    vertex(int a)
    {
        v = a;
        dw = 0;
    }

    ll distto_a(int a)
    {
        if(!dw)
        {
            dijkstra();
            dw = 1;
        }
        return dist[a];
    }
};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> s >> t >> u >> v;

    s--; t--; u--; v--;
    vector<vertex> ver;
    for(int i=0; i<n; i++)
    {
        vertex a(i);
        ver.push_back(a);
    }

    while(m--)
    {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        graf[a].push_back({c, b});
        graf[b].push_back({c, a});
    }

    ll ans=ver[u].distto_a(v);

    for(int i=0; i<n; i++)
    {
        for(int j=i; j<n; j++)
        {
            if(ver[s].distto_a(i)+ver[i].distto_a(j)+ver[j].distto_a(t) == ver[s].distto_a(t))
            {
                ans = min(ans, ver[v].distto_a(i)+ver[u].distto_a(j));
                ans = min(ans, ver[u].distto_a(i)+ver[v].distto_a(j));
            }
        }
    }

    cout << ans;
    return 0;
}

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