Submission #1341976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1341976		cansu_mutlu	Olympic Bus (JOI20_ho_t4)	C++20	11 / 100	72 ms	3612 KiB

ho_t4

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int mxn = 2e3+3;
int n;
vector<array<int,2>> a[mxn+1];
int bul(int i)
{
    
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    cin >> n >> m;
    vector<array<int,4>> nw(m);

    for(int i=0;i<m;i++)
    {
        int u,v,c,d;
        cin >> u >> v >> c >> d;
        a[u].push_back({v,c});
        nw[i] = {u,v,c,d};
    }
    vector<vector<int>> d(n+1,vector<int>(n+1,0));
    for(int i=1;i<=n;i++)
    {
        vector<int> dist(n+1,1e18);
    dist[i] = 0;
    priority_queue<array<int,2>> pq;
    pq.push({0,i});
    while(pq.size())
    {
        int s = pq.top()[1];
        pq.pop();
        for(auto k:a[s])
        {
            int x = k[0],w = k[1];
            if(w==1e18) continue;
            if(dist[x]>(dist[s]+w))
            {
                dist[x] = dist[s]+w;
                pq.push({-dist[x],x});
            }
        }
    }
    d[i] = dist;
    }
    int ans = min((int)1e18,d[1][n]+d[n][1]);
    int sum = d[1][n]+d[n][1];
    for(int b=0;b<m;b++)
    {
        int u = nw[b][0],v = nw[b][1],c = nw[b][2],e = nw[b][3];
        int cur = min(d[1][v]+c+d[u][n],d[1][n])+min(d[n][1],d[n][v]+c+d[u][1])+e;
        ans = min(ans,cur);
    }
    if(ans==1e18) cout << -1 << endl;
    else cout << ans << endl;
}

Compilation message (stderr)

ho_t4.cpp: In function 'long long int bul(long long int)':
ho_t4.cpp:10:1: warning: no return statement in function returning non-void [-Wreturn-type]
   10 | }
      | ^

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