Submission #1115051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115051		AdamGS	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1100 ms	3500 KiB

ho_t4

#include <iostream>
#include <functional>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    int n,m;
    cin >> n >> m;
    vector<int> U(m),V(m),C(m),D(m);
    for (int i=0; i<m; i++){
        cin >> U[i] >> V[i] >> C[i] >> D[i];
    }
    int64_t wyn=1e18;
    for (int i=0; i<m+1; i++){
        vector<vector<pair<int64_t,int64_t>>> gr(n+1);
        int64_t akt;
        for (int j=0; j<m; j++){
            if (j==i){
                gr[V[j]].push_back({C[j],U[j]});
                akt=D[j];
            }
            else gr[U[j]].push_back({C[j],V[j]});
        }
        /*cout << "\n===================================\n";
        for (int j=1; j<n+1; j++){
            cout << j << ":\n";
            for (auto k:gr[j]) cout << k.second << ' ' << k.first << '\n';
            cout << '\n';
        }
        cout << "===================================\n";
        cout << "===================================\n";*/
        priority_queue<pair<int64_t,int64_t>,vector<pair<int64_t,int64_t>>,greater<pair<int64_t,int64_t>>> q;
        q.push({0,1});
        vector<int64_t> odw(n+1,-1);
        while (q.size()){
            pair<int64_t,int64_t> aktq=q.top();
            q.pop();
            if (odw[aktq.second]!=-1) continue;
            odw[aktq.second]=aktq.first;
            //cout << '\n' << aktq.first << ' ' << aktq.second << '\n';
            for (auto j:gr[aktq.second]){
                //cout << i << '\n';
                //cout << j.first << ' ' << j.second << ' ' << odw[j.second] << '\n';
                if (odw[j.second]==-1){
                    //cout << j.first << ' ' << j.second << '\n';
                    q.push({j.first+aktq.first,j.second});
                }
                //else cout << j.first << ' ' << j.second << '\n';
            }
        }
        //cout << '\n' << odw[n]+akt << '\n';
        //if (odw[n]==-1) continue;
        q.push({0,n});
        vector<int64_t> odw1(n+1,-1);
        while (q.size()){
            pair<int64_t,int64_t> aktq=q.top();
            q.pop();
            if (odw1[aktq.second]!=-1) continue;
            odw1[aktq.second]=aktq.first;
            //cout << '\n' << aktq.first << ' ' << aktq.second << '\n';
            for (auto j:gr[aktq.second]){
                //cout << i << '\n';
                //cout << j.first << ' ' << j.second << ' ' << odw1[j.second] << '\n';
                if (odw1[j.second]==-1){
                    //cout << j.first << ' ' << j.second << '\n';
                    q.push({j.first+aktq.first,j.second});
                }
                //else cout << j.first << ' ' << j.second << '\n';
            }
        }
        //cout << 'a' << odw1[3];
        if (i==m) akt=0;
        //cout << '\n' << odw[n] << ' ' <<akt << ' ' << odw1[1] << '\n';
        if (odw1[1]==-1 or odw[n]==-1) continue;
        wyn=min(wyn,odw[n]+odw1[1]+akt);
    }
    if (wyn==1e18) cout << -1;
    else cout << wyn;
    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:76:35: warning: 'akt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |         wyn=min(wyn,odw[n]+odw1[1]+akt);

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