제출 #407254

#제출 시각아이디문제언어결과실행 시간메모리
407254nguotCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
334 ms24752 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;}) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rnd(int l,int r){return l+rng()%(r-l+1);} #define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define fori(x,a,b) for (int x=a;x<=b;x++) #define ford(x,a,b) for (int x=a;x>=b;x--) #define forv(a,b) for(auto&a:b) #define fi first #define se second #define pb push_back #define ii pair<int,int> #define all(a) a.begin(),a.end() #define reset(f, x) memset(f, x, sizeof(f)) #define getbit(x,i) ((x>>i)&1) #define batbit(x,i) (x|(1ll<<i)) #define tatbit(x,i) (x&~(1<<i)) #define gg exit(0); const int maxn = 2e5 + 10; int n,m,s,t,x,y; vector<ii> ke[maxn]; vector<int> dij(int s) { vector<int> f(n+5,1e15); priority_queue<ii,vector<ii>,greater<ii> > h; h.push({0,s}); while(!h.empty()) { ii u = h.top(); h.pop(); int umin = u.se,dmin = u.fi; forv(v,ke[umin]) if(f[v.fi] > dmin + v.se) { f[v.fi] = dmin + v.se; h.push({f[v.fi],v.fi}); } } return f; } void sub1() { vector<int> fs,ft,fy; fs = dij(s); ft = dij(t); fy = dij(y); int kq = 1e15; fori(i,1,n) if(fs[i]+ft[i]==fs[t]) kq=min(kq,fy[i]); cout<<kq; } main() { //freopen("task.inp","r",stdin); fasty; cin>>n>>m; cin>>s>>t; cin>>x>>y; fori(i,1,m) { int u,v,c;cin>>u>>v>>c; ke[u].pb({v,c}),ke[v].pb({u,c}); } if(s==x) sub1(); } /* chon 1 dg di ngan nhat tu s->t,cho tat cac canh tren dg di nay = 0 sao cho dg di ngan nhat tu u->v la MIN */ //https://oj.uz/problem/view/JOI18_commuter_pass

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

commuter_pass.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...