Submission #1036055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036055		_no_name	Robot (JOI21_ho_t4)	C++17	0 / 100	63 ms	27152 KiB

Main

///hihi PhongVan cbhk64
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define fo(i, l, r) for(int i = l; i <= r; i++)
#define foi(i, l, r) for(int i = l; i >= r; i--)
#define elif else if
#define el cout << endl
#define pii pair<int, int>
#define mx(x, y) max(x, y)
#define fi first
#define se second
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define ll long long
#define pob pop_back
#define bs binary_search
#define vii vector<int>
#define int long long
#define getbit(j, i) (j >> i) &1
#define fillchar(a,x) memset(a, x, sizeof (a))
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int N = 1e5 + 6;
const int mod = 1e9 + 7;
const int base = 31;
const int inf = 1e9;
int n, m;
struct canh{
    int u, v, color, cost;
}e[N];
int insub = 1;
bool vis[N];
vector<int> g[N];
void dfs(int u, int par){
    vis[u] = 1;
    for(auto v:g[u]){
        if(v == par) continue;
        if(!vis[v]){
            vis[v] = 1;
            dfs(v, u);
        }
    }
}
int d[N];
vector<pii> edge[N];
struct cmp{
    bool operator()(pii a, pii b){
        return a.se > b.se;
    }
};
void dijkstra(){
    fo(i, 1, n) d[i] = 1e18;
    d[1] = 0;
    priority_queue<pii, vector<pii>, cmp> q;
    q.push({1, d[1]});
    while(!q.empty()){
        int u = q.top().first;q.pop();
        if(vis[u] == 1) continue;
        vis[u] = 1;
        for(auto it : edge[u]){
            int v = it.first;
            int w = it.second;
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                q.push({v, d[v]});
            }
        }
    }
}
unordered_map<int, int> mp[N];
signed main()
{
   
    faster
    cin >> n >> m;
    fo(i, 1, m){
        int x, y, z, t;
        cin >> x >> y >> z >> t;
        mp[x][z]++;
        mp[y][z]++;
        e[i] = {x, y, z, t};
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, -1);
    if(!vis[n]) return cout << -1, 0;
    fo(i, 1, m){
        int u = e[i].u;
        int v = e[i].v;
        int c = e[i].color;
        int p = e[i].cost;
        if(mp[u][c] == 1){
            edge[u].push_back({v, 0});
        }
        else edge[u].push_back({v, p});
        if(mp[v][c] == 1) edge[v].push_back({u, 0});
        else edge[v].push_back({u, p});
    }
    fo(i, 1, n) vis[i] = 0;
    dijkstra();
    cout << d[n];
    return 0;
}

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