Submission #921568

#	Time	Username	Problem	Language	Result	Execution time	Memory
921568		dosts	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	1085 ms	262144 KiB

ho_t4

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
const int inf = 1e18,MOD = 1e9+7,N = 5000;
 
struct Edge{
    int v,c,r,idx;
};
 
void solve() {
    int n,m;
    cin >> n >> m;
    vector<Edge> edges[n+1],revedges[n+1];    
    for (int i=1;i<=m;i++) {
        int u,v,c,r;
        cin >> u >> v >> c >> r;
        edges[u].push_back({v,c,r,i});
        revedges[v].push_back({u,c,r,i});
    }
    int dp[n+1][m+1][2];
    for (int i=1;i<=n;i++) {
        for (int j=0;j<=m;j++) {
            dp[i][j][0] = dp[i][j][1] = inf;
        }
    }
    dp[1][0][0] = 0;
    using wtf = pair<pii,pii>;
    priority_queue<wtf,vector<wtf>,greater<wtf>> pq;
    pq.push({{1,0},{0,0}});
    while (!pq.empty()) {
        int node = pq.top().first.first;
        int reversed = pq.top().first.second;
        bool touch = pq.top().second.first;
        int cc = pq.top().second.second;
        pq.pop();
        if (dp[node][reversed][touch] < cc) continue;
        for (auto it : edges[node]) {
            int go = it.v;
            int idx = it.idx;
            int cost = it.c;
            if (idx == reversed) continue;
            if (dp[node][reversed][touch]+cost < dp[go][reversed][touch|(go == n)]) {
                dp[go][reversed][touch|(go==n)] = dp[node][reversed][touch]+cost;
                pq.push({{go,reversed},{touch|(go==n),dp[node][reversed][touch]+cost}});
            }
        }
        for (auto it : revedges[node]){
            if (reversed && it.idx != reversed) continue;
            int go = it.v;
            int cost = it.c;
            int revcost = it.r;
            int REAL = dp[node][reversed][touch]+cost+revcost*(reversed!=it.idx);
            if (REAL < dp[go][it.idx][touch|(go==n)]) {
                dp[go][it.idx][touch|(go==n)] = REAL;
                pq.push({{go,it.idx},{touch|(go==n),REAL}});
            }
        }
    }
 
    int ans = 1e18;
    for (int i=0;i<=m;i++) {
        ans = min(ans,dp[1][i][1]);
    }
    cout << ((ans==1e18)?-1:ans) << '\n';
}   
    
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
	while (t --> 0) solve();
}

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