이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Cookie197
// the people who invented competitive programming must be ******* crazy
// why am i still here suffering while i can do something else more valuable?
// WHY???
//#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include<numeric>
#include<random>
using namespace std;
#define Why_does_competitive_programming_even_exist ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<ll,ll>
#define pdd pair<double ,double>
#define mp make_pair
//#define mod 998244353
#define mod 1000000007
#define endl "\n"
#define inf (ll)1e18
#define out(x) cout << #x << " = " << x <<endl;
#define out2(a,b) cout<< #a << "[" << b << "]" << " = " << a[b] << endl;
#define outp(x) cout << #x << " first = " << x.first << " second = " << x.second << endl
#define mt(a,b,c) mp(a,mp(b,c))
int n,m,S,T,U,V;
vector<pii> adj[100005]; // node, dist
ll distS[100005], distT[100005], distU[100005], distV[100005], ans;
ll floyd[305][305];
void dijkstra(int start, ll dist[]){
for (int i=1;i<=n;i++) dist[i] = -1;
priority_queue<pii, vector<pii>, greater<pii> > pq;
pq.push(mp(0,start));
while(pq.size()){
int node = pq.top().second;
ll d = pq.top().first;
pq.pop();
if (dist[node] != -1) continue;
dist[node] = d;
for (pii p:adj[node]){
int u = p.first;
ll wei = p.second;
pq.push(mp(wei+d, u));
}
}
}
ll dp[2][100005];
bool vis[100005];
ll f(int start, int end){
for (int i=1;i<=n;i++) dp[0][i] = dp[1][i] = inf, vis[i] = false;
// dist, node, parent
priority_queue<pair<ll,pii>, vector<pair<ll,pii> >, greater<pair<ll,pii> > > pq;
pq.push(mt(0,start,0));
while(pq.size()){
ll d; int node, parent;
d = pq.top().first, node = pq.top().second.first, parent = pq.top().second.second;
pq.pop();
}
}
signed main(){
Why_does_competitive_programming_even_exist;
cin>>n>>m>>S>>T>>U>>V;
if (n>300) return 0;
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) floyd[i][j] = (i==j ? 0 : inf);
for (int i=1;i<=m;i++){
int a,b; ll c; cin>>a>>b>>c;
adj[a].push_back(mp(b,c));
adj[b].push_back(mp(a,c));
floyd[a][b] = floyd[b][a] = c;
}
//dijkstra(S,distS), dijkstra(V,distV), dijkstra(U,distU), dijkstra(T,distT);
//ans = distU[V];
for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){
floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j]);
}
ll ans = floyd[U][V];
for (int x=1;x<=n;x++) for (int y=1;y<=n;y++) {
if (floyd[S][x] + floyd[x][y] + floyd[y][T] == floyd[S][T]) ans = min(ans, floyd[U][x] + floyd[y][V]);
}
for (int x=1;x<=n;x++) for (int y=1;y<=n;y++) {
if (floyd[S][x] + floyd[x][y] + floyd[y][T] == floyd[S][T]) ans = min(ans, floyd[V][x] + floyd[y][U]);
}
cout<<ans<<endl;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'long long int f(int, int)':
commuter_pass.cpp:69:12: warning: variable 'd' set but not used [-Wunused-but-set-variable]
69 | ll d; int node, parent;
| ^
commuter_pass.cpp:69:19: warning: variable 'node' set but not used [-Wunused-but-set-variable]
69 | ll d; int node, parent;
| ^~~~
commuter_pass.cpp:69:25: warning: variable 'parent' set but not used [-Wunused-but-set-variable]
69 | ll d; int node, parent;
| ^~~~~~
commuter_pass.cpp:75:1: warning: no return statement in function returning non-void [-Wreturn-type]
75 | }
| ^
# | 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... |