제출 #939288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
939288		weakweakweak	Robot (JOI21_ho_t4)	C++17	100 / 100	359 ms	96976 KiB

Main

//直接抄解，因為我笨
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define fs first
#define sc second

int n, m;
int vis[510000] = {0}, dis[510000];
vector< pair<int,pii> > e[510000];
vector< pii > ne[510000];

signed main () {
    //輸入
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c, k;
        cin >> a >> b >> c >> k;
        e[a] . push_back({c,{b,k}});
        e[b] . push_back({c,{a,k}});
    }

    //建圖
    int now = n + 1;
    for (int i = 1; i <= n; i++) {
        //操作1
        for (auto [c, p] : e[i]) ne[i] . push_back(p);
        //操作2、先操作1再操作2
        map<int, vector<pii>>mp;
        for (auto [c, p] : e[i]) mp[c] . push_back(p);
        for (auto [c, vv] : mp) {
            ++now;
            int sum = 0;
            for (auto [j, w] : vv) sum += w;
            for (auto [j, w] : vv) {
                //操作2
                ne[i] . push_back({j, sum - w});
                //先1再2
                ne[now] . push_back({j, sum - w});
                ne[j] . push_back({now, 0});
            } 
        }
    }

    // Dijkstra and output
    memset(dis, 63, sizeof(dis));
    int inf = dis[0];
    dis[1] = 0;
    priority_queue< pii, vector<pii>, greater<pii> > pq;
    pq.push({0, 1});
    while (pq.size()) {
        auto [wow, i] = pq.top(); 
        pq.pop();
        if (vis[i]) continue;
        vis[i] = 1;
        for (auto [j, w] : ne[i]) {
            if (dis[i] + w < dis[j]) {
                dis[j] = dis[i] + w;
                pq.push({dis[j], j});
            }
        }
    }
    if (dis[n] >= inf / 2) dis[n] = -1;
    cout << dis[n] << '\n';
}

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