제출 #1292353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292353		KhanhDang	Robot (JOI21_ho_t4)	C++20	34 / 100	126 ms	29432 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define     ll long long
#define    pll pair<ll, ll>
#define    pii pair<int, int>
#define     fi first
#define     se second
#define all(v) (v).begin(), (v).end()
#define Unique(v) sort(all(v)); (v).erase(unique(all(v)), (v).end());

const int N = 1e5 + 5;

int n, m;

#define tup tuple<int, int, int>
vector<tup> adj[N];

vector<ll> dist[N][2];

ll cost[N];

vector<int> match[N];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "robot1"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    if (fopen("task.inp", "r")) {
        freopen("task.inp", "r", stdin);
        freopen("task.out", "w", stdout);
    }

    cin>>n>>m;
    for (int i = 1; i <= m; i++) {
        int u, v, c, p; cin>>u>>v>>c>>p;

        adj[u].emplace_back(v, c, p);
        adj[v].emplace_back(u, c, p);

        match[u].push_back(adj[v].size() - 1);
        match[v].push_back(adj[u].size() - 1);
    }

    if (n == 1) return cout<<0, 0;
    if (adj[1].empty()) return cout<<-1, 0;

    dist[1][0].resize(adj[1].size(), 0);
    dist[1][1].resize(adj[1].size(), 0);

    for (int i = 2; i <= n; i++)
        for (int t = 0; t <= 1; t++)
            dist[i][t].resize(adj[i].size(), 1e16);

                //   dist  u    t   from
    #define Tup tuple<ll, int, int, int>
    priority_queue<Tup, vector<Tup>, greater<Tup>> pq;
    pq.push({0, 1, 0, 0});

    while (!pq.empty()) {
        auto [d, u, t, from] = pq.top();
        pq.pop();

        if (d != dist[u][t][from])
            continue;

        if (u == n) return cout<<d, 0;

        int m = adj[u].size();

        for (int i = 0; i < m; i++) {
            auto [v, c, p] = adj[u][i];
            cost[c] = 0;
        }

        for (int i = 0; i < m; i++) {
            if (t == 1 && i == from)
                continue;

            auto [v, c, p] = adj[u][i];
            cost[c] += p;
        }

        //cout<<u<<'\n';

        for (int i = 0; i < m; i++) {
            if (t == 1 && i == from)
                continue;

            auto [v, c, p] = adj[u][i];

            ll Cost = cost[c] - p;
            if (dist[v][0][match[u][i]] > d + Cost) {
                dist[v][0][match[u][i]] = d + Cost;
                pq.push({d + Cost, v, 0, match[u][i]});
                //cout<<v<<' '<<u<<' '<<0<<' '<<d + Cost<<'\n';
            }

            Cost = p;
            if (dist[v][1][match[u][i]] > d + Cost) {
                dist[v][1][match[u][i]] = d + Cost;
                pq.push({d + Cost, v, 1, match[u][i]});
                //cout<<v<<' '<<u<<' '<<1<<' '<<d + Cost<<'\n';
            }
        }
    }

    cout<<-1;

    cerr<<setprecision(3)<<fixed<<"Time elapsed: "<< 1.0 * clock() / CLOCKS_PER_SEC <<"s\n";
}

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

Main.cpp: In function 'int main()':
Main.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 34 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42