제출 #1086190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1086190		kiethm07	Commuter Pass (JOI18_commuter_pass)	C++11	31 / 100	215 ms	30760 KiB

commuter_pass

#include <bits/stdc++.h>

#define pii pair<int,int>
#define pli pair<long long,int>
#define iii pair<int,pii>
#define fi first
#define se second

#define vi vector<int>
#define vii vector<pii>
#define pb(i) push_back(i)
#define all(x) x.begin(),x.end()

#define TEXT "a"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll inf = 1e15 + 5;
const ld eps = 1e-8;
const double pi = acos(-1);
const int N = 1e5 + 5;

vector<pii> a[N];
vector<int> b[N], c[N];
vector<ll> dS, dT, dX, dY;
ll f[N], g[N];
int n,m;
int s,t,x,y;

void dijkstra(int s, vector<ll>& d){
    d.resize(n + 5,inf);
    priority_queue<pli,vector<pli>,greater<pli>> pq;
    d[s] = 0;
    pq.push(pli(0,s));
    while(!pq.empty()){
        int u = pq.top().se;
        ll dis = pq.top().fi;
        pq.pop();
        if (dis > d[u]) continue;
        for (int i = 0; i < a[u].size(); i++){
            int v = a[u][i].fi;
            int w = a[u][i].se;
            if (d[u] + w < d[v]){
                d[v] = d[u] + w;
                pq.push(pli(d[v],v));
            }
        }
    }
}

void buildGraph(){
    for (int u = 1; u <= n; u++){
        for (int i = 0; i < a[u].size(); i++){
            int v = a[u][i].fi;
            int w = a[u][i].se;
            if (dS[v] == dS[u] + w && dS[t] == dS[u] + w + dT[v]){
                b[u].push_back(v);
                c[v].push_back(u);
                //cout << u << " " << v << " " << w << "\n";
            }
        }
    }
}

void cal(int u){
    if (f[u] != inf) return;
    f[u] = dX[u];
    g[u] = dY[u];
    for (int v : c[u]){
        cal(v);
        f[u] = min(dX[u], f[v]);
        g[u] = min(dY[u], g[v]);
    }
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen(TEXT".inp","r")){
        freopen(TEXT".inp","r",stdin);
        freopen(TEXT".out","w",stdout);
    }
    cin >> n >> m;
    cin >> s >> t >> x >> y;
    for (int i = 1; i <= m; i++){
        int u,v,w;
        cin >> u >> v >> w;
        a[u].pb(pii(v,w));
        a[v].pb(pii(u,w));
    }
    dijkstra(s, dS);
    dijkstra(t, dT);
    dijkstra(x, dX);
    dijkstra(y, dY);
    buildGraph();
    for (int i = 1; i <= n; i++) f[i] = g[i] = inf;
    cal(t);
    ll res = dX[y];
    for (int i = 1; i <= n; i++){
        res = min(res, f[i] + g[i]);
        //cout << i << " " << f[i] << " " << g[i] << " " << f[i] + g[i] << "\n";
    }
    cout << res << "\n";
    return 0;
}

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

commuter_pass.cpp: In function 'void dijkstra(int, std::vector<long long int>&)':
commuter_pass.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int i = 0; i < a[u].size(); i++){
      |                         ~~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'void buildGraph()':
commuter_pass.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i = 0; i < a[u].size(); i++){
      |                         ~~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(TEXT".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(TEXT".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45