이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
const int maxn = 2e5+10;
int n,m,s,t,U,V;
vector <pii> edge[maxn];
ll dis[4][maxn];
pq <pll,vector<pll>,greater<pll> > q;
ll ans[maxn][2][2];
void dijkstra(int sta,int id) {
memset(dis[id],inf,sizeof(dis[id]));
dis[id][sta]=0;
q.push({0,sta});
while (!q.empty()) {
ll u = q.top().se,d=q.top().fi;
q.pop();
if (dis[id][u]!=d) continue;
for (pii v:edge[u]) {
if (dis[id][v.fi]>d+v.se) {
dis[id][v.fi]=d+v.se;
q.push({d+v.se,v.fi});
}
}
}
}
ll getdp(int u,int flag1,int flag2) {
if (u==t) return flag1*dis[2][u]+flag2*dis[3][u];
if (ans[u][flag1][flag2]!=-1) return ans[u][flag1][flag2];
ll ret = 1e16;
for (pii v:edge[u]) {
if (dis[1][v.fi]+v.se+dis[0][u]!=dis[0][t]) continue;
ret=min(ret,getdp(v.fi,flag1,flag2));
if (flag1==1) ret=min(ret,getdp(v.fi,0,flag2)+dis[2][u]);
if (flag2==1) ret=min(ret,getdp(v.fi,flag1,0)+dis[3][u]);
}
return ans[u][flag1][flag2]=ret;
}
int main() {
// freopen("input.txt","r",stdin);
std::ios::sync_with_stdio(false);cin.tie(0);
memset(ans,-1,sizeof(ans));
cin>>n>>m>>s>>t>>U>>V;
rep(i,0,m) {
int u,v,w;
cin>>u>>v>>w;
edge[u].pb({v,w});
edge[v].pb({u,w});
}
dijkstra(U,2);
dijkstra(s,0);
dijkstra(t,1);
dijkstra(V,3);
// debug(dis[2][V]);
cout<<min(dis[2][V],getdp(s,1,1));
return 0;
}
# | 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... |