이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 2;
ll n, m, a, b, c, d, dist[4][maxn], dp[4][maxn], u, v, w, res;
bool visited[maxn], avail[maxn];
struct Edge
{
ll u, v, w;
}edge[maxn];
vector<int> adj[maxn], dag[maxn], lst;
struct Item
{
ll u, dist;
bool operator < (const Item& other) const
{
return dist > other.dist;
}
};
priority_queue<Item> pq;
bool minimize (ll &a, ll b)
{
if (a == -1 || a > b)
{
a = b;
return true;
}
return false;
}
void topo (int u)
{
avail[u] = true;
for (int v : dag[u])
if (!avail[v]) topo(v);
lst.push_back(u);
}
void dijkstra (int x, int u)
{
memset(visited, 0, sizeof(visited));
for (int i = 1; i <= n; i++) dist[x][i] = -1;
dist[x][u] = 0;
pq.push({u, 0});
while (!pq.empty())
{
int u = pq.top().u;
pq.pop();
if (visited[u]) continue;
visited[u] = true;
for (int i : adj[u])
{
int v = edge[i].u ^ edge[i].v ^ u;
if (minimize(dist[x][v], dist[x][u] + edge[i].w)) pq.push({v, dist[x][v]});
}
}
}
int main ()
{
//freopen(task".INP", "r", stdin);
//freopen(task".OUT", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> a >> b >> c >> d;
for (int i = 1; i <= m; i++)
{
cin >> u >> v >> w;
edge[i] = {u, v, w};
adj[u].push_back(i);
adj[v].push_back(i);
}
dijkstra(0, a);
dijkstra(1, b);
dijkstra(2, c);
dijkstra(3, d);
for (int u = 1; u <= n; u++)
{
for (int i : adj[u])
{
int v = edge[i].u ^ edge[i].v ^ u;
if (dist[0][u] + dist[1][v] + edge[i].w == dist[0][b]) dag[u].push_back(v);
}
}
topo(a);
reverse(lst.begin(), lst.end());
for (int i = 1; i <= n; i++) dp[2][i] = dp[3][i] = -1;
for (int u : lst)
{
minimize(dp[2][u], dist[2][u]);
for (int v : dag[u]) minimize(dp[2][v], dp[2][u]);
}
for (int u : lst)
{
minimize(dp[3][u], dist[3][u]);
for (int v : dag[u]) minimize(dp[3][v], dp[3][u]);
}
res = dist[2][d];
for (int i = 1; i <= n; i++)
{
if (dp[2][i] != -1) res = min(res, dp[2][i] + dist[3][i]);
if (dp[3][i] != -1) res = min(res, dp[3][i] + dist[2][i]);
}
cout << res;
}
# | 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... |