제출 #699833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
699833		qwerasdfzxcl	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	256 ms	3016 KiB

ho_t4

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
constexpr ll INF = 1e18;
int n, m, U[50050], V[50050], C[50050], D[50050];
pair<ll, int> adj[202][202];
ll d1[202], d2[202], d3[202], d4[202], dist1[202], dist2[202];
int visited[202], chk[50050], par[202];

void dijkstra(int s, ll dist[], int *chk = 0, int e = 0){
    fill(dist+1, dist+n+1, INF);
    fill(visited+1, visited+n+1, 0);

    dist[s] = 0;
    for (int i=1;i<=n;i++){
        ll mn = INF + 1, v = -1;
        for (int j=1;j<=n;j++) if (!visited[j] && dist[j] < mn){
            mn = dist[j];
            v = j;
        }

        assert(v!=-1);
        visited[v] = 1;

        for (int j=1;j<=n;j++) if (!visited[j] && dist[j] > dist[v] + adj[v][j].first){
            dist[j] = dist[v] + adj[v][j].first;
            par[j] = adj[v][j].second;
        }
    }

    if (chk && dist[e] < INF){
        for (int i=e;i!=s;i=U[par[i]]){
            chk[par[i]] = 1;
        }
    }
}

ll init(){
    for (int i=1;i<=n;i++) fill(adj[i]+1, adj[i]+n+1, pair<ll, int>(INF, -1));
    for (int i=1;i<=m;i++){
        adj[U[i]][V[i]] = min(adj[U[i]][V[i]], pair<ll, int>(C[i], i));
    }

    dijkstra(1, d1, chk, n);
    dijkstra(n, d3, chk, 1);

    for (int i=1;i<=n;i++) fill(adj[i]+1, adj[i]+n+1, pair<ll, int>(INF, -1));
    for (int i=1;i<=m;i++){
        adj[V[i]][U[i]] = min(adj[V[i]][U[i]], pair<ll, int>(C[i], i));
    }

    dijkstra(n, d2);
    dijkstra(1, d4);

    return d1[n] + d3[1];
}

ll solve(int idx){
    for (int i=1;i<=n;i++) fill(adj[i]+1, adj[i]+n+1, pair<ll, int>(INF, -1));
    for (int i=1;i<=m;i++){
        if (i!=idx) adj[U[i]][V[i]] = min(adj[U[i]][V[i]], pair<ll, int>(C[i], i));
        else adj[V[i]][U[i]] = min(adj[V[i]][U[i]], pair<ll, int>(C[i], i));
    }

    dijkstra(1, dist1);
    dijkstra(n, dist2);
    return dist1[n] + dist2[1];
}

int main(){
    scanf("%d %d", &n, &m);
    for (int i=1;i<=m;i++) scanf("%d %d %d %d", U+i, V+i, C+i, D+i);

    ll ans = init();
    for (int i=1;i<=m;i++){
        if (chk[i]) ans = min(ans, solve(i) + D[i]);
        else ans = min(ans, min(d1[n], d1[V[i]] + C[i] + d2[U[i]]) + min(d3[1], d3[V[i]] + C[i] + d4[U[i]]) + D[i]);
    }

    printf("%lld\n", ans>=INF?-1:ans);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp:73:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     for (int i=1;i<=m;i++) scanf("%d %d %d %d", U+i, V+i, C+i, D+i);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63