oj.uz

Submission #477383

# Submission time Handle Problem Language Result Execution time Memory
477383 2021-10-01T21:40:10 Z Qw3rTy Robot (JOI21_ho_t4) C++11
0 / 100
 1 ms 1104 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Incorrect 1 ms 1104 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 680 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Incorrect 1 ms 1104 KB Output isn't correct
8 Halted 0 ms 0 KB -