이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
const long long LL_INF = 1000000000ll * 1000000000;
struct Edge {
int v,w;
bool in;
Edge() {};
Edge(int _v,int _w,bool _in) : v(_v), w(_w), in(_in) {};
};
vector<Edge> adj[MAXN+1];
long long dis[4][MAXN+1];
int n,m;
int s,t,l,r;
void dijkstra(int st,int id) {
for (int i=1;i<=n;i++) dis[id][i] = LL_INF;
dis[id][st] = 0;
priority_queue<pair<long long,int>> pq;
pq.push(make_pair(0,st));
while (pq.size()) {
int u = pq.top().second;
long long cur_d = -pq.top().first;
pq.pop();
if (cur_d > dis[id][u]) continue;
for (int i=0;i<adj[u].size();i++) {
int v = adj[u][i].v, w = adj[u][i].w;
if (dis[id][v] > cur_d + w) {
dis[id][v] = cur_d + w;
pq.push(make_pair(-dis[id][v],v));
}
}
}
}
vector<int> topo;
int pos_topo[MAXN+1];
int vst[MAXN+2];
long long dp[2][MAXN+1];
void dfs(int u) {
vst[u] = 1;
for (int i=0;i<adj[u].size();i++) {
if (!adj[u][i].in) continue;
int v = adj[u][i].v;
if (!vst[v]) dfs(v);
}
topo.push_back(u);
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> m;
cin >> s >> t >> l >> r;
for (int i=1;i<=m;i++) {
int x,y,w; cin >> x >> y >> w;
adj[x].push_back(Edge(y,w,0));
adj[y].push_back(Edge(x,w,0));
}
dijkstra(s,0);
dijkstra(t,1);
dijkstra(l,2);
dijkstra(r,3);
long long shortest = dis[0][t];
long long ans = dis[2][r];
for (int u=1;u<=n;u++) {
for (int i=0;i<adj[u].size();i++) {
int v = adj[u][i].v, w = adj[u][i].w;
if (dis[0][u] + dis[1][v] + w == shortest) {
adj[u][i].in = 1;
}
}
}
dfs(s);
topo.push_back(0);
reverse(topo.begin(),topo.end());
for (int i=1;i<topo.size();i++) {
pos_topo[topo[i]] = i;
dp[0][i] = dp[1][i] = LL_INF;
}
dp[0][1] = dis[2][topo[1]];
dp[1][1] = dis[3][topo[1]];
for (int i=1;i<topo.size();i++){
int u = topo[i];
dp[0][i] = min(dp[0][i], dis[2][u]);
dp[1][i] = min(dp[1][i], dis[3][u]);
ans = min(ans,dp[0][i] + dis[3][u]);
ans = min(ans,dp[1][i] + dis[2][u]);
for (int j=0;j<adj[u].size();j++) {
if (!adj[u][j].in) continue;
int v = adj[u][j].v;
int pos_v = pos_topo[v];
dp[0][pos_v] = min({dp[0][pos_v],dp[0][i]});
dp[1][pos_v] = min({dp[1][pos_v],dp[1][i]});
}
}
cout << ans;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void dijkstra(int, int)':
commuter_pass.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i=0;i<adj[u].size();i++) {
| ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i=0;i<adj[u].size();i++) {
| ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i=0;i<adj[u].size();i++) {
| ~^~~~~~~~~~~~~~
commuter_pass.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i=1;i<topo.size();i++) {
| ~^~~~~~~~~~~~
commuter_pass.cpp:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i=1;i<topo.size();i++){
| ~^~~~~~~~~~~~
commuter_pass.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int j=0;j<adj[u].size();j++) {
| ~^~~~~~~~~~~~~~
# | 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... |