제출 #477383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
477383		Qw3rTy	Robot (JOI21_ho_t4)	C++11	0 / 100	1 ms	1104 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define INF 1e16
#define pi pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int maxN = 2e3+5;
struct cmp{
    bool operator() (pi a, pi b){
        return a.fi > b.fi;
    }
};
struct edge{
    int to,col,p;
    edge(){};
    edge(int to, int col, int p){
        this -> to = to;
        this -> col = col;
        this -> p = p;
    }
};
vector<edge> adj[maxN];
vector<pi> adj2[maxN];
int N,M;
int dist[maxN];
bool vis[maxN];
int f[maxN][maxN]; //f[i][j] = # of roads with color j at node i
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("../test.in","r",stdin);
    cin >> N >> M;
    for(int i = 1; i <= M; ++i){
        int a,b,c,p; cin >> a >> b >> c >> p;
        adj[a].pb(edge(b,c,p));
        adj[b].pb(edge(a,c,p));
        ++f[a][c]; ++f[b][c];
    }
    //construct adj2
    for(int i = 1; i <= N; ++i){
        int MIN = INF; //MIN = min (roads with color j at node i) for 1 <= j <= M
        for(int j = 1; j <= M; ++j){
            MIN = min(MIN,f[i][j]);
        }
        for(edge e: adj[i]){
            adj2[i].pb(pi(e.to,min(MIN+1,f[i][e.col]-1)*e.p));
        }
    }
    //dijk
    for(int i = 1; i <= N; ++i)dist[i] = INF;
    memset(vis,false,sizeof(vis));
    priority_queue<pi,vector<pi>,cmp> Q;
    Q.push(pi(0,1));
    dist[1] = 0;
    while(!Q.empty()){
        pi p = Q.top(); Q.pop();
        int loc = p.se;
        if(vis[loc])continue;
        vis[loc] = true;
        for(auto x: adj2[loc]){
            if(dist[loc] + x.se < dist[x.fi]){
                dist[x.fi] = dist[loc] + x.se;
                if(!vis[x.fi]){
                    Q.push(pi(dist[x.fi],x.fi));
                }
            }
        }
    }
    if(dist[N] == INF)cout << -1 << '\n';
    else cout << dist[N] << '\n';
}

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