제출 #491814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
491814		mickytanawin	Robot (JOI21_ho_t4)	C++17	34 / 100	3068 ms	48148 KiB

Main

#include <bits/stdc++.h>
using namespace std;

enum state {
    ME = 0, OTHER = 1
};

#define f first
#define s second
typedef long long lli;
typedef pair<int, int> pii;
typedef pair<int, lli> pil;
typedef tuple<int, int, int> tiii;
typedef tuple<lli, int, state, int> tlisi;

const int N = 1e5 + 5;
const int M = 2e5 + 5;

map<int, pil> sum[N];
map<int, lli> distMe[N];
set<int> visitedMe[N];
vector<pii> adj[N];
lli distOther[N];
bool visitedOther[N];
pii edges[M];

void addColorEdge(int u, int c, int w){
    map<int, pil>::iterator itr = sum[u].find(c);
    if(itr == sum[u].end()){
        sum[u][c].f = 1;
        sum[u][c].s = w;
    } else {
        ++(itr -> s.f);
        itr -> s.s += w;
    }
}

int main(){

    int nVertex, nEdge;
    scanf("%d%d", &nVertex, &nEdge);
    for(int i = 1; i <= nEdge; ++i){
        int u, v, c, w;
        scanf("%d%d%d%d", &u, &v, &c, &w);
        edges[i] = pii(c, w);
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
        addColorEdge(u, c, w);
        addColorEdge(v, c, w);
        //printf("edges[%d]: (%d, %d)\n", i, edges[i].f, edges[i].s);
    }
    for(int u = 1; u <= nVertex; ++u){
        distOther[u] = 1e18;
    }
    priority_queue<tlisi, vector<tlisi>, greater<tlisi>> pq;
    distOther[1] = 0;
    pq.emplace(distOther[1], 1, OTHER, 0);
    while(!pq.empty()){
        //printf("dist:%lld\n", get<0>(pq.top()));
        int u = get<1>(pq.top());
        state us = get<2>(pq.top());
        int ui = get<3>(pq.top());
        int uc = edges[ui].f;
        int uw = edges[ui].s;
        //printf("u:%d us:%d ui:%d uc:%d uw:%d\n", u, us, ui, uc, uw);
        pq.pop();
        if(us == ME){
            //printf("ME\n");
            if(u == nVertex){
                cout << distMe[u][ui];
                return 0;
            }
            if(visitedMe[u].find(ui) != visitedMe[u].end()){
                continue;
            }
            visitedMe[u].insert(ui);
            for(pii nxt : adj[u]){
                int v = nxt.f;
                int i = nxt.s;
                int c = edges[i].f;
                int w = edges[i].s;
                //printf("v:%d c:%d w:%d\n", v, c, w);
                //printf("sum[u][c].f:%d\n", sum[u][c].f);
                if(sum[u][c].f == 1 || uc == c && sum[u][c].f == 2){
                    //printf("Change to 0\n");
                    if(!visitedOther[v] && distMe[u][ui] < distOther[v]){
                        distOther[v] = distMe[u][ui];
                        pq.emplace(distOther[v], v, OTHER, i);
                    }
                    continue;
                }
                lli cost = w;
                //printf("COST ME:%lld\n", cost);
                if(visitedMe[v].find(i) == visitedMe[v].end() && (distMe[v].find(i) == distMe[v].end() || distMe[u][ui] + cost < distMe[v][i])){
                    distMe[v][i] = distMe[u][ui] + cost;
                    pq.emplace(distMe[v][i], v, ME, i);
                }
                cost = sum[u][c].s - w;
                if(uc == c){
                    cost -= uw;
                }
                //printf("COST OTHER:%lld\n", cost);
                if(!visitedOther[v] && distMe[u][ui] + cost < distOther[v]){
                    distOther[v] = distMe[u][ui] + cost;
                    pq.emplace(distOther[v], v, OTHER, i);
                }
            }
        } else {
            //printf("OTHER\n");
            if(u == nVertex){
                cout << distOther[u];
                return 0;
            }
            if(visitedOther[u]){
                continue;
            }
            visitedOther[u] = true;
            for(pii nxt : adj[u]){
                int v = nxt.f;
                int i = nxt.s;
                int c = edges[i].f;
                int w = edges[i].s;
                //printf("v:%d\n", v);
                if(sum[u][c].f == 1){
                    //printf("change to 0\n");
                    if(!visitedOther[v] && distOther[u] < distOther[v]){
                        distOther[v] = distOther[u];
                        pq.emplace(distOther[v], v, OTHER, i);
                    }
                    continue;
                }
                lli cost = w;
                //printf("COST ME:%lld\n", cost);
                if(visitedMe[v].find(i) == visitedMe[v].end() && (distMe[v].find(i) == distMe[v].end() || distOther[u] + cost < distMe[v][i])){
                    distMe[v][i] = distOther[u] + cost;
                    pq.emplace(distMe[v][i], v, ME, i);
                }
                cost = sum[u][c].s - w;
                //printf("COST OTHER:%lld\n", cost);
                if(!visitedOther[v] && distOther[u] + cost < distOther[v]){
                    distOther[v] = distOther[u] + cost;
                    pq.emplace(distOther[v], v, OTHER, i);
                }
            }
        }
    }
    cout << "-1";

    return 0;
}

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

Main.cpp: In function 'int main()':
Main.cpp:84:48: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   84 |                 if(sum[u][c].f == 1 || uc == c && sum[u][c].f == 2){
      |                                        ~~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d%d", &nVertex, &nEdge);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d%d%d%d", &u, &v, &c, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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