이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//code
#define fl(i,x,y,z) for(int i=x;i<=y;i=i+z)
#define fn(i,x,y,z) for(int i=x;i>=y;i=i-z)
#define rep(i,x,y) for(int i=x;i<y;i=i+1)
#define all(v) v.begin(),v.end()
#define pb push_back
#define tle cout<<"tle"<<endl
#define edl cout<<"\n"
#define el "\n"
#define getbit(x,i) ((x>>i)&1)
#define bitcnt __builtin_popcount
//ham
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define ld long double
#define inf 0x3f3f3f3f
//#define int long long
using namespace std;
const int N=1e5+5;
const ll mod=1e9+7;
int n,m;
int u,v,s,t;
vector <pii> e[N];
int ds[N],dt[N],du[N],dv[N];
int f1[N],f2[N];
void inp()
{
cin>>n>>m;
cin>>s>>t;
cin>>u>>v;
fl(i,1,m,1)
{
int x,y,c; cin>>x>>y>>c;
e[x].pb({y,c});
e[y].pb({x,c});
}
}
void dij(int p,int d[])
{
// fl(i,1,n,1) d[i]=1e9;
// d[p]=0;
// priority_queue <pii,vector <pii>,greater<pii>> q;
// q.push({d[p],p});
// while (!q.empty())
// {
// int x=q.top().se;
// int c=q.top().fi;
// q.pop();
// if (c>d[x]) continue;
// for (auto it: e[x])
// {
// int y=it.fi,w=it.se;
// if (d[y]>d[x]+w)
// {
// d[y]=d[x]+w;
// q.push({d[y],y});
// }
// }
// }
for(int i=0; i<=n; i++) d[i] = 1e18;
d[p] = 0;
priority_queue<pii> Q;
Q.push({0, p});
while(Q.size()){
int du, u;
tie(du, u) = Q.top();
Q.pop();
du = -du;
if(du != d[u]) continue;
for(pii edge: e[u]){
int v, c;
tie(v, c) = edge;
if(d[v] > du + c){
d[v] = du + c;
Q.push({-d[v], v});
}
}
}
}
void sol()
{
dij(s, ds);
dij(t, dt);
dij(u, du);
dij(v, dv);
vector<int> vt(n);
for(int i=0; i<n; i++) vt[i] = i + 1;
sort(vt.begin(), vt.end(), [&](const int &a, const int &b) -> bool {return ds[a] < ds[b];});
memset(f1, 0x3f, sizeof f1);
memset(f2, 0x3f, sizeof f2);
int ans = du[v];
for(int u: vt) if(ds[u] + dt[u] == ds[t]){
f1[u] = du[u];
f2[u] = dv[u];
for(pii edge: e[u]){
int v, c;
tie(v, c) = edge;
if(ds[v] + c == ds[u]){
f1[u] = min(f1[v], f1[u]);
f2[u] = min(f2[v], f2[u]);
}
}
ans = min({ans, f1[u] + dv[u], f2[u] + du[u]});
}
cout<<ans;
}
signed main()
{
// freopen("task.inp","r",stdin);
// freopen("task.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
inp();
sol();
return 0;
}
/* /\_/\
( ._. )
/ >v< \
*/
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void dij(int, int*)':
commuter_pass.cpp:63:36: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
63 | for(int i=0; i<=n; i++) d[i] = 1e18;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |