제출 #1342010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1342010		cansu_mutlu	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	71 ms	3820 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]);
    vector<vector<int>> cnt(n+1,vector<int>(n+1,0));
    if(ans!=1e18)
    {
        cout << 0 << endl;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j = 1;j<=n;j++)
        {

            if(i==j)
            {
                cnt[i][j] = 1;
                continue;
            }
            if(d[i][j]<1e18) cnt[i][j]++;
            for(int k = 1;k<=n;k++)
            {
                if(i!=k && k!=j && d[i][k]<1e18 && d[k][j]<1e18) cnt[i][j]++;
            }
            
        }
    }
    for(int i=0;i<m;i++)
    {
        int u = nw[i][0],v = nw[i][1],c = nw[i][2],d = nw[i][3];
        int a = cnt[1][n]-cnt[1][u]*cnt[v][n]+cnt[1][v]*cnt[u][n];
        int b = cnt[n][1]-cnt[n][u]*cnt[v][1]+cnt[n][v]*cnt[u][1];
       // cout << a << 
        if(a&&b) ans = min(ans,c+d);
    }
    if(ans==1e18) cout << -1 << endl;
    else cout << ans << endl;
}

컴파일 시 표준 에러 (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: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63