| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 99454 | psmao | Commuter Pass (JOI18_commuter_pass) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<long long,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<59;
const db Inf = 1e20;
const db eps = 1e-9;
void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}
const int maxn = 100050;
int n, m, s, t, u, v, head[maxn], tot, pre[maxn];
struct edge{int next, to, w;}e[maxn<<2];
ll dist[maxn];
bool inq[maxn];
priority_queue<pii,vector<pii>,greater<pii> > pq;
inline void add_edge(int u, int v, int w)
{
e[tot] = (struct edge){head[u], v, w}; head[u] = tot++;
e[tot] = (struct edge){head[v], u, w}; head[v] = tot++;
}
inline ll dijkstra(int s, int t)
{
pq.push(mp(0ll, s));
fo(i,1,n) dist[i] = INF;
dist[s] = 0;
while(!pq.empty())
{
int h = pq.top().se; pq.pop(); inq[h] = false;
for(int i = head[h]; i != -1; i = e[i].next)
{
int v = e[i].to;
if(dist[v] > dist[h] + e[i].w)
{
dist[v] = dist[h] + e[i].w;
pre[v] = i;
if(!inq[v]) inq[v] = true, pq.push(mp(dist[v], v));
}
}
}
return dist[t];
}
inline nvoid back_track(int t)
{
if(t == s) return;
e[pre[t]].w = 0;
back_track(e[pre[t]^1].to);
}
void read(int &x)
{
x = 0; char c = '.';
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}
int main()
{
#ifdef MPS
fp("1.in","r",stdin);
fp("1.out","w",stdout);
#endif
read(n); read(m);
read(s); read(t); read(u); read(v);
memset(head, -1, sizeof(head));
fo(i,1,m)
{
int u, v, w;
read(u); read(v); read(w);
add_edge(u, v, w);
}
dijkstra(s, t);
back_track(t);
pf("%lld\n",dijkstra(u, v));
return 0;
}