제출 #1130174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130174		randomxsoul	Olympic Bus (JOI20_ho_t4)	C++20	5 / 100	1095 ms	10564 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define vi vector<int>
#define vs vector<string>
#define vb vector<bool>
#define vpi vector<pi>
#define pb push_back
#define all(a) (a).begin(), (a).end()
const int mod = 1e16 + 7;
const int N = 205;
int n, m;
vector<multiset<int>> g(N);
vector<vector<multiset<int>>> c(N, vector<multiset<int>>(N));

int dijkstra(int i, int j)
{
    vi dist(n + 1, mod);
    dist[i] = 0;
    queue<int> q;
    q.push(i);
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        for (auto ch : g[v])
        {
            int x = *c[v][ch].begin();
            if (dist[ch] > dist[v] + x)
            {
                dist[ch] = dist[v] + x;
                q.push(ch);
            }
        }
    }
    return dist[j];
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    vector<vi> roads(m);
    for (int i = 0; i < m; i++)
    {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        roads[i].pb(x);
        roads[i].pb(y);
        roads[i].pb(a);
        roads[i].pb(b);
        g[x].insert(y);
        c[x][y].insert(a);
    }
    int ans = dijkstra(1, n) + dijkstra(n, 1);
    for (auto p : roads)
    {
        int x = p[0], y = p[1], a = p[2], b = p[3];
        g[x].erase(g[x].find(y));
        g[y].insert(x);
        c[x][y].erase(c[x][y].find(a));
        c[y][x].insert(a);
        ans = min(ans, dijkstra(1, n) + dijkstra(n, 1) + b);
        g[y].erase(g[y].find(x));
        g[x].insert(y);
        c[y][x].erase(c[y][x].find(a));
        c[x][y].insert(a);
    }
    cout << (ans >= mod ? -1 : ans) << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63