Submission #364387

#	Time	Username	Problem	Language	Result	Execution time	Memory
364387		shafinalam	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	706 ms	5212 KiB

ho_t4

#include <bits/stdc++.h>
 
using namespace std;
const int mxn = 1e5+5;
typedef long long ll;
#define inf 1e17
typedef pair<ll,ll>pii;
ll cost[mxn];
ll dir[mxn];
 
struct data
{
    int u, v;
    ll c, d;
};
vector<pii>adj[205];
vector<pii>rev[205];
vector<data>edge;
ll dis[5][205];
int path[3][205];
int n, m;
 
void dijkstra1(int src, int pos)
{
 
    vector<int>vis(n+1, 0);
    dis[pos][src] = 0;
    priority_queue<pii>pq;
    pq.push({0LL, src});
    while(!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(auto it : adj[u]) {
            ll w = cost[it.second];
            int v = it.first;
            if(dis[pos][u]+w<dis[pos][v]) {
                dis[pos][v] = dis[pos][u]+w;
                path[pos][v] = it.second;
                pq.push({-dis[pos][v], v});
            }
        }
    }
    return;
}
void dijkstra2(int src, int pos)
{
    vector<int>vis(n+1, 0);
    dis[pos][src] = 0;
    priority_queue<pii>pq;
    pq.push({0LL, src});
    while(!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(auto it : rev[u]) {
            ll w = cost[it.second];
            int v = it.first;
            if(dis[pos][u]+w<dis[pos][v]) {
                dis[pos][v] = dis[pos][u]+w;
                pq.push({-dis[pos][v], v});
            }
        }
    }
    return;
}
ll dijkstra(int src, int idx)
{
    vector<ll>dp(n+5, inf);
    vector<bool>vis(n+5, 0);
    dp[src] = 0;
    priority_queue<pii>pq;
    pq.push({0, src});
    while(!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(auto it : adj[u]) {
            if(idx==it.second) continue;
            int v = it.first;
            ll w = cost[it.second];
            if(dp[u]+w<dp[v]) {
                dp[v] = dp[u]+w;
                pq.push({-dp[v], v});
            }
        }
        if(u==edge[idx].v) {
            int x = edge[idx].v;
            int y = edge[idx].u;
            ll w = edge[idx].c;
            if(dp[x]+w<dp[y]) {
                dp[y] = dp[x]+w;
                pq.push({-dp[y], y});
            }
        }
    }
    if(src==1) return dp[n];
    return dp[1];
 
}
int main()
{
 
    scanf("%d%d", &n, &m);
    for(int i = 0; i < 5; i++) {
        for(int r = 0; r <= n; r++) dis[i][r] = inf;
    }
 
    for(int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d%lld%lld", &u, &v, &cost[i], &dir[i]);
        adj[u].push_back({v, i});
        rev[v].push_back({u, i});
        edge.push_back({u, v, cost[i], dir[i]});
    }
    dijkstra1(1, 0);
    dijkstra1(n, 1);
    dijkstra2(1, 2);
    dijkstra2(n, 3);
    ll ans = dis[0][n]+dis[1][1];
    for(int i = 0; i < m; i++) {
        int u = edge[i].u;
        int v = edge[i].v;
        ll c = edge[i].c;
        ll d = edge[i].d;
        ll res = d;
        /*
        if(i==2) {
            cout << res << '\n';
        }
        */
        if(path[0][v]==i) {
            res+=dijkstra(1, i);
        }
 
        else {
            res+=min(dis[0][n], dis[0][v]+dis[3][u]+c);
        }
        /*
        if(i==2) {
            cout << res << '\n';
        }
        */
        if(path[1][v]==i) {
            res+=dijkstra(n, i);
        }
        else {
            res+=min(dis[1][1], dis[1][v]+dis[2][u]+c);
        }
        /*
        if(i==2) {
            cout << res << '\n';
        }
        */
        //cout << res << '\n';
        ans = min(ans, res);
    }
 
    if(ans>=inf) {
        cout << -1 << '\n';
    }
    else {
        cout << ans << '\n';
    }
    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |         scanf("%d%d%lld%lld", &u, &v, &cost[i], &dir[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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