Submission #469709

#	Time	Username	Problem	Language	Result	Execution time	Memory
469709		MohamedFaresNebili	Robot (JOI21_ho_t4)	C++14	0 / 100	16 ms	6808 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll  = long long;
using ld  = long double;

#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin() , (x).end()

const ll MOD = 998244353;
const long double EPS = 0.000000001;
const double PI = 3.14159265358979323846;
const int nx[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
const int ny[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

ll n, m, color[100005], cost[1005][2005]; bool vis[100005];
vector<pair<int, pair<int, int>>>adj[100005];
bool dfs(int v) {
    if(v==n) return true;
    vis[v]=true;
    for(auto u:adj[v]) {
        if(vis[u.ss.ff]) continue;
        if(dfs(u.ss.ff)) return true;
    }
    return false;
}

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int l=0;l<m;l++) {
        ll a, b, c, p; cin>>a>>b>>c>>p; color[l]=c;
        adj[a].pb({l, {b, p}}); adj[b].pb({l, {a, p}});
        cost[a][c]+=p; cost[b][c]+=p;
    }
    if(!dfs(1)) { cout<<-1; return 0; }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
    pq.push({0, 1}); vector<ll>d(n+1, MOD); d[1]=0;
    while(!pq.empty()) {
        ll a=pq.top().ss, w=pq.top().ff; pq.pop();
        if(d[a]<w) continue;
        for(auto u:adj[a]) {
            ll curr=INT_MAX;
            for(int l=1;l<=m;l++) {
                if(l==color[u.ff]) curr=min(curr, cost[a][l]-u.ss.ss);
                else curr=min(curr, cost[a][l]+u.ss.ss);
            }
            if(d[a]+curr<d[u.ss.ff]) {
                d[u.ss.ff]=d[a]+curr;
                pq.push({d[u.ss.ff], u.ss.ff});
            }
        }
    }
    cout<<d[n]<<'\n';
    return 0;
}

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