Submission #959765

#	Time	Username	Problem	Language	Result	Execution time	Memory
959765		OIaspirant2307	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	469 ms	6764 KiB

ho_t4

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <utility>
using namespace std;
#define int long long
#define pi pair<int,int>

const int N = 203, M = 5 * 10^4 + 3;
const int inf = 1e17;
vector<vector<int>> dis(N, vector<int>(N, inf));
multiset<pi> g[N];
vector<int> wt;
vector<int> cost;
int n, m;

int dijkstra(int x, int y){
    vector<int> dist(n + 1, inf);
    vector<bool> vis(n + 1, 0);
    priority_queue<pi, vector<pi>, greater<pi>> ms;
    ms.push({0, x});
    dist[x] = 0;
    while (!ms.empty()) {
        auto p = ms.top();
        int v = p.second;
        ms.pop();
        if(vis[v])
            continue;
        vis[v] = true;
        for (auto ch : g[v]){
            int ch_v = ch.first;
            int ch_wt = wt[ch.second];
            if (dist[v] + ch_wt < dist[ch_v]){
                dist[ch_v] = dist[v] + ch_wt;
                ms.push({dist[ch_v], ch_v});
            }
        }
    }
    return dist[y];
}

signed main()
{
    cin >> n >> m;
    wt.resize(m);
    cost.resize(m);
    for (int i = 1; i <= n; i++)
    {
        dis[i][i] = 0;
    }
    pi edges[m];
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v >> wt[i] >> cost[i];
        g[u].insert({v, i});
        edges[i] = {u, v};
        dis[u][v] = min(dis[u][v], wt[i]);
    }

    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }

    int ans = min(inf, dis[1][n] + dis[n][1]);
    for (int i = 0; i < m; i++)
    {
        int u = edges[i].first, v = edges[i].second;

        if (min(dis[1][n], dis[1][v] + wt[i] + dis[u][n]) +
                min(dis[n][1], dis[n][v] + wt[i] + dis[u][1]) + cost[i] <
            ans)
        {

            g[u].erase(g[u].find({v, i}));
            g[v].insert({u, i});
            ans = min(ans, cost[i] + dijkstra(1, n) + dijkstra(n, 1));
            g[v].erase(g[v].find({edges[i].first, i}));
            g[u].insert({v, i});
        }
    }
    if (ans == inf)
    {
        cout << -1;
        return (int)0;
    }
    cout << ans;
}

Compilation message (stderr)

ho_t4.cpp:10:33: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   10 | const int N = 203, M = 5 * 10^4 + 3;
      |                               ~~^~~

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