oj.uz

Submission #534237

# Submission time Handle Problem Language Result Execution time Memory
534237 2022-03-08T02:40:31 Z Biaz Robot (JOI21_ho_t4) C++17
0 / 100
 141 ms 19952 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
#define X first
#define Y second
#define ist insert
#define pii pair<int,int>
typedef long long ll;

using namespace std;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
const int INF=170000000000000;//2147483647;
const int MOD=998244353;//1000000007;
const int N=100005;

struct I{
    int u,c,p;
};
int n,m;
vector<I> e[N];
int d[N];
priority_queue<pii,vector<pii>,greater<pii>> pq;
map<int,int> mp[N];
void dij(){
    fill(d,d+N,INF);
    d[1]=0;
    pq.push({0,1});
    while (pq.size()){
        auto [w,v]=pq.top();pq.pop();
        if (d[v]<w) continue;
        for (auto [u,c,p]:e[v]){
            if (d[u]>(mp[v][c]-1)+w){
                d[u]=(mp[v][c]-1)+w;
                pq.push({d[u],u});
            }
        }
    }
    if (d[n]==INF) cout <<-1;
    else cout <<d[n];
}
void sol(){
    cin >>n>>m;
    for (int i=0,u,v,c,p;i<m;i++){
       cin >>u>>v>>c>>p;
       e[u].pb({v,c,p});
       e[v].pb({u,c,p});
       mp[u][c]++;
       mp[v][c]++;
    }
    dij();
}
signed main()
{
    int _=1;
    //cin >>_;
    while (_--) sol();
    return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 7 ms 8116 KB Output is correct
3 Incorrect 6 ms 8012 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 19952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 7 ms 8116 KB Output is correct
3 Incorrect 6 ms 8012 KB Output isn't correct
4 Halted 0 ms 0 KB -