Submission #224106

#	Time	Username	Problem	Language	Result	Execution time	Memory
224106		dantoh000	Olympic Bus (JOI20_ho_t4)	C++14	5 / 100	1084 ms	1796 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef pair<ii,ii> i4;
i4 G[50005];
vector<ii> adjlist[205];
int ans = 2000000000;
int n,m;
int dist[205];
priority_queue<ii,vector<ii>, greater<ii> > pq;
int test(){
    for (int i = 1; i <= n; i++) adjlist[i].clear();
    for (int i = 0; i < m; i++){
        int u = G[i].first.first;
        int v = G[i].first.second;
        int c = G[i].second.first;
        adjlist[u].push_back({v,c});
    }
    memset(dist,-1,sizeof(dist));
    dist[1] = 0;
    pq.push({0,1});
    while (pq.size()){
        ii cur = pq.top(); pq.pop();
        int d = cur.first, u = cur.second;
        if (dist[u] < d) continue;
        for (auto v: adjlist[u]){
            int newdist = dist[u]+v.second;
            if (dist[v.first] == -1 || newdist < dist[v.first]){
                dist[v.first] = newdist;
                pq.push({dist[v.first],v.first});
            }
        }
    }
    int L = dist[n];
    memset(dist,-1,sizeof(dist));
    dist[n] = 0;
    pq.push({0,n});
    while (pq.size()){
        ii cur = pq.top(); pq.pop();
        int d = cur.first, u = cur.second;
        if (dist[u] < d) continue;
        for (auto v: adjlist[u]){
            int newdist = dist[u]+v.second;
            if (dist[v.first] == -1 || newdist < dist[v.first]){
                dist[v.first] = newdist;
                pq.push({dist[v.first],v.first});
            }
        }
    }
    int R = dist[1];
    if (L == -1 || R == -1) return -1;
    else return L+R;
}

int main(){
    scanf("%d%d",&n,&m);
    for (int i = 0; i < m; i++){
        int u,v,c,d;
        scanf("%d%d%d%d",&u,&v,&c,&d);
        G[i].first.first = u;
        G[i].first.second = v;
        G[i].second.first = c;
        G[i].second.second = d;
    }
    int x = test();
    //printf("noflip, %d\n",x);
    if (x != -1) ans = min(ans,x);
    for (int i = 0; i<  m; i++){
        int cost = G[i].second.second;
        swap(G[i].first.first,G[i].first.second);
        int r = test();
        swap(G[i].first.first,G[i].first.second);
        //printf("%d %d\n",cost,r);
        if (r == -1) continue;
        ans = min(ans,cost+r);
    }
    if (ans == 2000000000){
        printf("-1");
        return 0;
    }
    else printf("%d \n",ans);


}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:57: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:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d",&u,&v,&c,&d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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