제출 #1291970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291970		trandangquang	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	424 ms	6296 KiB

ho_t4

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

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=50505;
const ll INF=1e18;

int n,m;
multiset<ii> adj[N];
int uu[N],vv[N],cc[N],dd[N];
ll d[202][202],dist[N];

ll dijkstra(int x, int y){
    foru(i,1,n) dist[i]=INF;
    priority_queue<ii,vector<ii>,greater<ii>>pq;
    dist[x]=0;
    pq.push({dist[x],x});
    while(pq.size()){
        auto [du,u]=pq.top(); pq.pop();
        if(du>dist[u]) continue;
        for(auto [v,w]:adj[u]){
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                pq.push({dist[v],v});
            }
        }
    }
    return dist[y];
}

void solve(){
    cin>>n>>m;

    foru(i,1,n) foru(j,1,n) d[i][j]=INF;

    foru(i,1,m){
        cin>>uu[i]>>vv[i]>>cc[i]>>dd[i];
        mini(d[uu[i]][vv[i]],cc[i]);
        adj[uu[i]].insert(ii(vv[i],cc[i]));
    }

    /// floyd
    foru(i,1,n) d[i][i]=0;
    foru(k,1,n){
        foru(i,1,n) foru(j,1,n){
            mini(d[i][j], d[i][k]+d[k][j]);
        }
    }

    ll res=d[1][n]+d[n][1];
    foru(i,1,m){
        ll go =min(d[1][n],d[1][vv[i]]+cc[i]+d[uu[i]][n]),
           ret=min(d[n][1],d[n][vv[i]]+cc[i]+d[uu[i]][1]);

        if(go+ret+dd[i]<res){
            adj[uu[i]].erase(adj[uu[i]].find(ii(vv[i],cc[i])));
            adj[vv[i]].insert(ii(uu[i],cc[i]));

            mini(res,dijkstra(1,n)+dijkstra(n,1)+dd[i]);

            adj[vv[i]].erase(adj[vv[i]].find(ii(uu[i],cc[i])));
            adj[uu[i]].insert(ii(vv[i],cc[i]));
        }
    }

    if(res>=INF) cout<<"-1\n";
    else cout<<res<<'\n';
}

int32_t main(){
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int tc=1; //cin>>tc;
    rep(i,tc){
        solve();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'int32_t main()':
ho_t4.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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