이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
#define llmax 9223372036854775807
//note: everything is one-indexed
lo nodes, edges, s,t,u,v, temp1,temp2,temp3;
vector<tuple<lo,lo,lo>>elist(200001);
vector<vector<pair<lo,lo>>>adjlist(100001);
int ucount = 0;
//ducks
lo dp(lo start, vector<bool> &visited, vector<lo> &distv, lo ans, vector<vector<int>> &usable_edges, vector<lo> &minnow)
{
if (visited[start])
{
//cout << "once, " << start << " " << visited[start];
return minnow[start];
}
visited[start] = true;
ans = distv[start];
//cout << ans;
for (int x: usable_edges[start])
{
//cout << start << " connects to " << x << " \n";
ans = min(ans,dp(x,visited,distv,ans,usable_edges,minnow));
}
//cout << "For starting node " << start << " : ";
//cout << ans << "\n";
minnow[start] = ans;
return ans;
}
void dijkstra(int n, vector<lo> &dist)
{
priority_queue<pair<lo,lo>, vector<pair<lo,lo>> , greater<pair<lo,lo>>>pq;
fill(dist.begin(),dist.end(),-1);
lo temp1,temp2,temp3,temp4;
pq.push(make_pair(0,n));
//cout << "pq: " << pq.top().first << " " << pq.top().second << "\n";
while (!pq.empty())
{
tie(temp1,temp2) = pq.top(); // cost, node
pq.pop();
if (dist[temp2] != -1) //already visited
{
continue;
}
dist[temp2] = temp1;
//cout << "Initialising " << temp2 << " to " << temp1 << "\n";
for (auto x : adjlist[temp2])
{
tie(temp3,temp4) = x; //cost, node
pq.push(make_pair(temp1 + temp3, temp4));
}
}
}
int main()
{
cin >> nodes >> edges >> s >> t >> u >> v;
//cout << "v: " << v << "\n";
vector<vector<vector<int>>>usable_edges(2, vector<vector<int>>(nodes + 1)); //direction used, diff direction
for (int a = 1; a <= edges; a++)
{
cin >> temp1 >> temp2 >> temp3;
adjlist[temp1].push_back(make_pair(temp3,temp2));
adjlist[temp2].push_back(make_pair(temp3,temp1));
elist[a] = make_tuple(temp1,temp2,temp3);
}
/*cout << "Outputting all edges: (cost,start,end)\n";
for (int a = 1; a <= nodes; a++)
{
for (auto x: adjlist[a])
{
int b,c;
tie(b,c) = x;
cout << b << " " << a << " " << c << "\n";
}
}*/
vector<lo>dists(nodes + 1),distu(nodes + 1),distt(nodes + 1),distv(nodes + 1);
dijkstra(s,dists);dijkstra(t,distt);dijkstra(u,distu);dijkstra(v,distv);
/*cout << "Outputting minimum distances from s: \n";
for (int a = 1; a <= nodes; a++)
{
cout << dists[a] << " ";
}
cout << " \nOutputting minimum distance from u ;)\n";
for (int a = 1; a <= nodes; a++)
{
cout << distu[a] << " ";
}
cout << " \n";*/
lo mind = distt[s];
//cout << "ans and mind: " << ans << " " << mind << "\n";
for (int a = 1; a <= edges; a++) //for each edge
{
tie(temp1,temp2,temp3) = elist[a]; //start,end,cost
if (dists[temp1] + distt[temp2] + temp3 == mind) //temp1 to temp2
{ //if edge can be used
usable_edges[0][temp1].push_back(temp2);
usable_edges[1][temp2].push_back(temp1);
ucount += 1;
}
else if (dists[temp2] + distt[temp1] + temp3 == mind)
{
usable_edges[0][temp2].push_back(temp1);
usable_edges[1][temp1].push_back(temp2);
ucount += 1;
}
}
/*for (int a = 1; a <= nodes; a++)
{
cout << a << " : ";
for (int b : usable_edges[a])
{
cout << b << " ";
}
cout << "\n";
}*/
/*cout << "distance from v \n\n";
for (int a = 1; a <= nodes; a++)
{
cout << "From node " << a << " : " << distv[a] << "\n";
}
cout << "distance from u ;)\n";
for (int a = 1; a <= nodes; a++)
{
cout << "From node " << a << " : " << distu[a] << "\n";
}*/
/*cout << "Outputting usable_edges: \n";
for (int a = 0; a < nodes; a++)
{
cout << a << " : ";
for (int x : usable_edges[1][a])
{
cout << x << " ";
}
cout << "\n";
}
for (int a = 0; a < nodes; a++)
{
cout << a << " : ";
for (int x : usable_edges[0][a])
{
cout << x << " ";
}
cout << "\n";
}*/
vector<bool> visited(nodes + 1);
vector<lo>minnow(nodes + 1);
fill(minnow.begin(),minnow.end(),-1);
long long ans = distv[u];
for (int b = 0; b < 2; b++)
{
fill(minnow.begin(),minnow.end(),-1);
fill(visited.begin(),visited.end(),false);
for (int a = 1; a <=nodes; a++)
{
//cout << a << " ";
ans = min(ans,distu[a] + dp(a,visited,distv,ans,usable_edges[b],minnow));
}
}
//cout << "Outputting: \n";
cout << ans;
}
# | 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... |