이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*input
6 7
1 6
4 5
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
1 4 1
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 100;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl
//Trace prints the name of the variable and the value.
int n, m, s, t, u, v, dists[N], distt[N];
vector< pii > adjlist[N];
priority_queue< pii, vector<pii>, greater<pii> >pq1;int dp[N][3];
void dij(int src, int dist[N])
{
for(int i=1;i<=n;i++) {dist[i]=inf;dp[i][0]=dp[i][1]=dp[i][2]=inf;}
dist[src]=0;pq1.push(mp(0, src));
while(!pq1.empty())
{
pii cur=pq1.top();pq1.pop();
if(cur.f>dist[cur.s]) continue;
for(auto j:adjlist[cur.s])
{
if(dist[j.f]>cur.f + j.s)
{
dist[j.f]=cur.f+j.s;pq1.push(mp(dist[j.f], j.f));
}
}
}
}
struct node
{
int i, j, cd;
};
node mn(int a, int b, int c)
{
node t;t.i=a;t.j=b;t.cd=c;return t;
}
struct comp
{
bool operator()(node a, node b)
{
if(a.cd==b.cd) return (b.j==1);
return a.cd>=b.cd;
}
};
priority_queue<node, vector<node>, comp> pq;
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n>>m>>s>>t>>u>>v;
for(int i=1;i<=m;i++)
{
int u, v, w;cin>>u>>v>>w;adjlist[u].push_back(mp(v, w));adjlist[v].push_back(mp(u, w));
}
dij(s, dists);dij(t, distt);
dp[u][0]=dp[u][1]=dp[u][2]=0;pq.push(mn(u, 0, 0));pq.push(mn(u, 1, 0));pq.push(mn(u, 2, 0));
while(!pq.empty())
{
node cur=pq.top();pq.pop();//cout<<cur.i<<" "<<cur.j<<endl;
if(cur.cd>dp[cur.i][cur.j]) continue;
for(auto j:adjlist[cur.i])
{
if(cur.j==1) {
if(dists[cur.i]+j.s+distt[j.f]==dists[t]||distt[cur.i]+j.s+dists[j.f]==dists[t]) j.s=0;
else if(dp[j.f][2]>cur.cd +j.s)
{
dp[j.f][2]=cur.cd +j.s;pq.push(mn(j.f, 2, cur.cd +j.s));continue;
}
}
int nd=cur.cd +j.s;
for(int nxt=cur.j;nxt<3;nxt++)
{
if(dp[j.f][nxt]>nd)
{
dp[j.f][nxt]=nd;pq.push(mn(j.f, nxt, nd));
}
}
}
}
cout<<min(dp[v][1], dp[v][2]);
}
# | 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... |