이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e5+5;
typedef long long ll;
#define inf 1e17
typedef pair<ll,ll>pii;
ll cost[mxn];
ll dir[mxn];
struct data
{
int u, v;
ll c, d;
};
vector<pii>adj[205];
vector<pii>rev[205];
vector<data>edge;
ll dis[5][205];
int path[3][205];
int n, m;
void dijkstra1(int src, int pos)
{
vector<int>vis(n+1, 0);
dis[pos][src] = 0;
priority_queue<pii>pq;
pq.push({0LL, src});
while(!pq.empty()) {
int u = pq.top().second;
pq.pop();
if(vis[u]) continue;
vis[u] = 1;
for(auto it : adj[u]) {
ll w = cost[it.second];
int v = it.first;
if(dis[pos][u]+w<dis[pos][v]) {
dis[pos][v] = dis[pos][u]+w;
path[pos][v] = it.second;
pq.push({-dis[pos][v], v});
}
}
}
return;
}
void dijkstra2(int src, int pos)
{
vector<int>vis(n+1, 0);
dis[pos][src] = 0;
priority_queue<pii>pq;
pq.push({0LL, src});
while(!pq.empty()) {
int u = pq.top().second;
pq.pop();
if(vis[u]) continue;
vis[u] = 1;
for(auto it : rev[u]) {
ll w = cost[it.second];
int v = it.first;
if(dis[pos][u]+w<dis[pos][v]) {
dis[pos][v] = dis[pos][u]+w;
pq.push({-dis[pos][v], v});
}
}
}
return;
}
ll dijkstra(int src, int idx)
{
vector<ll>dp(n+5, inf);
vector<bool>vis(n+5, 0);
dp[src] = 0;
priority_queue<pii>pq;
pq.push({0, src});
while(!pq.empty()) {
int u = pq.top().second;
pq.pop();
if(vis[u]) continue;
vis[u] = 1;
for(auto it : adj[u]) {
if(idx==it.second) continue;
int v = it.first;
ll w = cost[it.second];
if(dp[u]+w<dp[v]) {
dp[v] = dp[u]+w;
pq.push({-dp[v], v});
}
}
if(u==edge[idx].v) {
int x = edge[idx].v;
int y = edge[idx].u;
ll w = edge[idx].c;
if(dp[x]+w<dp[y]) {
dp[y] = dp[x]+w;
pq.push({-dp[y], y});
}
}
}
if(src==1) return dp[n];
return dp[1];
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < 5; i++) {
for(int r = 0; r <= n; r++) dis[i][r] = inf;
}
for(int i = 0; i < m; i++) {
int u, v;
scanf("%d%d%lld%lld", &u, &v, &cost[i], &dir[i]);
adj[u].push_back({v, i});
rev[v].push_back({u, i});
edge.push_back({u, v, cost[i], dir[i]});
}
dijkstra1(1, 0);
dijkstra1(n, 1);
dijkstra2(1, 2);
dijkstra2(n, 3);
ll ans = dis[0][n]+dis[1][1];
for(int i = 0; i < m; i++) {
int u = edge[i].u;
int v = edge[i].v;
ll c = edge[i].c;
ll d = edge[i].d;
ll res = d;
/*
if(i==2) {
cout << res << '\n';
}
*/
if(path[0][v]==1) {
res+=dijkstra(1, i);
}
else {
res+=min(dis[0][n], dis[0][v]+dis[3][u]+c);
}
/*
if(i==2) {
cout << res << '\n';
}
*/
if(path[1][v]==1) {
res+=dijkstra(n, i);
}
else {
res+=min(dis[1][1], dis[1][v]+dis[2][u]+c);
}
/*
if(i==2) {
cout << res << '\n';
}
*/
//cout << res << '\n';
ans = min(ans, res);
}
if(ans>=inf) {
cout << -1 << '\n';
}
else {
cout << ans << '\n';
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
107 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
114 | scanf("%d%d%lld%lld", &u, &v, &cost[i], &dir[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |