oj.uz

Submission #921562

# Submission time Handle Problem Language Result Execution time Memory
921562 2024-02-04T06:39:17 Z dosts Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 262144 KB 
#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}});
            }
        }
        if (!reversed) {
            for (auto it : revedges[node]){
                int go = it.v;
                int cost = it.c;
                int revcost = it.r;
                if (dp[node][reversed][touch]+cost+revcost < dp[go][it.idx][touch|(go==n)]) {
                    dp[go][it.idx][touch|(go==n)] = dp[node][reversed][touch]+cost+revcost;
                    pq.push({{go,it.idx},{touch|(go==n),dp[node][reversed][touch]+cost+revcost}});
                }
            }
        }
    }

    int ans = 2e18;
    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.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4816 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 561 ms 12336 KB Output is correct
4 Correct 620 ms 13492 KB Output is correct
5 Correct 68 ms 2260 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 600 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 4820 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Execution timed out 1069 ms 161684 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4816 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 561 ms 12336 KB Output is correct
4 Correct 620 ms 13492 KB Output is correct
5 Correct 68 ms 2260 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -