이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl
#define int ll
struct node {
vector<pri> adj;
int val;
pri sx = {1e18,1e18},sy = {1e18,1e18};
};
pri compx(pri a, pri b) {
if (a.first < b.first) return a;
if (a.first==b.first) return a.second > b.second ? b : a;
return b;
}
pri compy(pri a,pri b) {
if (a.second < b.second) return a;
if (a.second == b.second) return a.first < b.first ? a : b;
return b;
}
int32_t main() {
int n,m;cin>>n>>m;
int s,t,u,v;cin>>s>>t>>u>>v;
vector<node> nodes(n);
for (int i = 0;i<m;i++) {
int a,b,c;cin>>a>>b>>c;
nodes[a-1].adj.push_back({b-1,c});
nodes[b-1].adj.push_back({a-1,c});
}
/* for (int i = 0;i<n;i++) {
cout<<i<<endl;
for (int j = 0;j<nodes[i].adj.size();j++) {
cout<<nodes[i].adj[j].first<<" "<<nodes[i].adj[j].second<<endl;
}
} */
auto dijkstra = [n,nodes](int start) {
vector<int> mp(n,1e18);
mp[start] = 0;
set<pri> q;
q.insert({0,start});
while (q.size()) {
auto f = *q.begin();
for (int i = 0;i<nodes[f.second].adj.size();i++) {
if (mp[nodes[f.second].adj[i].first] > (mp[f.second] + nodes[f.second].adj[i].second)) {
mp[nodes[f.second].adj[i].first] = mp[f.second] + nodes[f.second].adj[i].second;
q.insert({mp[f.second] + nodes[f.second].adj[i].second,nodes[f.second].adj[i].first});
}
}
q.erase(q.begin());
}
return mp;
};
vector<int> dijkS,dijkU,dijkV;
dijkS = dijkstra(s-1);
dijkU = dijkstra(u-1);
dijkV = dijkstra(v-1);
vector<pri> dijk(n);
for (int i = 0;i<n;i++) {
dijk[i] = {dijkS[i],i};
}
sort(dijk.begin(),dijk.end());
nodes[s-1].sx = nodes[s-1].sy = {dijkU[s-1],dijkV[s-1]};
for (int i = 0;i<dijk.size();i++) {
for (int j = 0;j<nodes[dijk[i].second].adj.size();j++) {
if (dijkS[nodes[dijk[i].second].adj[j].first] + nodes[dijk[i].second].adj[j].second == dijk[i].first) {
nodes[dijk[i].second].sx = compx(nodes[dijk[i].second].sx,nodes[nodes[dijk[i].second].adj[j].first].sx);
nodes[dijk[i].second].sy = compy(nodes[dijk[i].second].sy,nodes[nodes[dijk[i].second].adj[j].first].sy);
//cout<<nodes[dijk[i].second].minY<<endl;
}
}
nodes[dijk[i].second].sx.first = min(nodes[dijk[i].second].sx.first,dijkU[dijk[i].second]);
nodes[dijk[i].second].sy.first = min(nodes[dijk[i].second].sy.first,dijkU[dijk[i].second]);
nodes[dijk[i].second].sx.second = min(nodes[dijk[i].second].sx.second,dijkV[dijk[i].second]);
nodes[dijk[i].second].sy.second = min(nodes[dijk[i].second].sy.second,dijkV[dijk[i].second]);
//nodes[dijk[i].second].sx = nodes[dijk[i].second].sy = {dijkU[dijk[i].second],dijkV[dijk[i].second]};
}
/* for (int i = 0;i<n;i++) {
cout<<i+1<<" -> "<<endl;
cout<<" "<<nodes[i].sx.first<<" "<<nodes[i].sx.second<<endl;
cout<<" "<<nodes[i].sy.first<<" "<<nodes[i].sy.second<<endl;
} */
int va = nodes[t-1].sx.first + nodes[t-1].sx.second;
int vb = nodes[t-1].sy.first + nodes[t-1].sy.second;
cout<<min(min(va,vb),dijkU[v-1])<<endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:59:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0;i<nodes[f.second].adj.size();i++) {
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:82:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0;i<dijk.size();i++) {
| ~^~~~~~~~~~~~
commuter_pass.cpp:83:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int j = 0;j<nodes[dijk[i].second].adj.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... |