Submission #224078

#	Time	Username	Problem	Language	Result	Execution time	Memory
224078		tqbfjotld	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	4 ms	384 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define INF 2000000009

int n,m;
int dist[205];
vector<pair<int,int> > adjl[205];
vector<pair<int,int> > rev[205];
int c[50005];
int d[50005];

int main(){
    scanf("%d%d",&n,&m);
    if (m<1000){
        for (int x = 0; x<m; x++){
            int a,b;
            scanf("%d%d%d%d",&a,&b,&c[x],&d[x]);
            adjl[a].push_back({b,x});
            rev[b].push_back({a,x});
        }
        int fans = INF;
        for (int cov = -1; cov<m; cov++){
            priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;

            for (int x = 0; x<=n; x++){
                dist[x] = INF;
            }
            dist[1] = 0;
            pq.push({0,1});
            while (!pq.empty()){
                int d = pq.top().first;
                int node = pq.top().second;
                pq.pop();
                if (d>dist[node]) continue;
                for (auto x : adjl[node]){
                    if (x.second==cov) continue;
                    if (dist[node]+c[x.second]<dist[x.first]){
                        dist[x.first] = dist[node]+c[x.second];
                        pq.push({dist[x.first],x.first});
                    }
                }
                for (auto x : rev[node]){
                    if (x.second!=cov) continue;
                    if (dist[node]+c[x.second]<dist[x.first]){
                        dist[x.first] = dist[node]+c[x.second];
                        pq.push({dist[x.first],x.first});
                    }
                }
            }
            int ans = dist[n];
            if (ans==INF) continue;
            for (int x = 0; x<=n; x++){
                dist[x] = INF;
            }
            dist[n] = 0;
            pq.push({0,n});
            while (!pq.empty()){
                int d = pq.top().first;
                int node = pq.top().second;
                pq.pop();
                if (d>dist[node]) continue;
                for (auto x : adjl[node]){
                    if (x.second==cov) continue;
                    if (dist[node]+c[x.second]<dist[x.first]){
                        dist[x.first] = dist[node]+c[x.second];
                        pq.push({dist[x.first],x.first});
                    }
                }
                for (auto x : rev[node]){
                    if (x.second!=cov) continue;
                    if (dist[node]+c[x.second]<dist[x.first]){
                        dist[x.first] = dist[node]+c[x.second];
                        pq.push({dist[x.first],x.first});
                    }
                }
            }
            fans = min(fans,ans+dist[1]+d[cov]);
        }
        printf("%d",fans==INF?-1:fans);
    }
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
ho_t4.cpp:17:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d%d%d",&a,&b,&c[x],&d[x]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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