Submission #1036060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036060		HNa_seawjing	Robot (JOI21_ho_t4)	C++14	0 / 100	353 ms	52292 KiB

Main

#include <bits/stdc++.h>
#define fo(i,m,n) for(int i=m;i<=n;i++)
#define fod(i,n,m) for(int i=n;i>=m;i--)
#define fo1(i,m,n,k) for(int i=m;i<=n;i=i+k)
#define fod1(i,n,m,k) for(int i=n;i>=m;i=i-k)
#define fol(i,m,n) for(long long i=m;i<=n;i++)
#define fodl(i,n,m) for(long long i=n;i>=m;i--)
#define fo1l(i,m,n,k) for(long long i=m;i<=n;i=i+k)
#define fod1l(i,n,m,k) for(long long i=n;i>=m;i=i-k)
#define lb lower_bound
#define ub upper_bound
#define pii pair <int,int>
#define vii vector<pii>
#define ll long long
#define fi first
#define se second
#define si size()
#define pb push_back
#define ppb pop_back()
#define fr front()
#define et empty()
#define bg begin()
#define ub upper_bound
#define lb lower_bound
#define ed end()
#define el endl
#define EL cout << '\n';
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
const int M = 1e3 + 5;
int n, m;
map <pii, int> dem;
struct zata{
    int u, v, c, val;
}d[10 * N];
bool kts2 = true;
void inp(){
    cin >> n >> m;
    fo(i, 1, m){
        cin >> d[i].u >> d[i].v >> d[i].c >> d[i].val;
        if(d[i].val != 1) kts2 = false;
        dem[{d[i].u, d[i].c}] += 1;
        dem[{d[i].v, d[i].c}] += 1;
    }
}
ll s[10 * N];
bool dd[10 * N];
vii adj[10 * N];
ll dfs1(int u, ll sum){
    if(u == n) return sum;
    ll mn = 1e18 + 19;
    for(pii it : adj[u]){
        int v = it.fi, val = it.se;
        if(dd[v]) continue;
        dd[v] = true;
        mn = min(mn, dfs1(v, sum + val));
        dd[v] = false;
    }
    return mn;
}
void dijsktra(int x){
    fo(i, 1, n){
        s[i] = 1e18;
        dd[i] = false;
    }
    s[x] = 0;
    priority_queue <pii, vector<pii>, greater <pii>> q;
    q.push({0, x});
	while(q.si){
		pii it = q.top();
		q.pop();
		int u = it.se;
		if(dd[u] == 1) continue;
		dd[u] = 1;
		for(pii wt : adj[u]){
			int v = wt.fi, val = wt.se;
			if(s[v] > s[u] + val){
				s[v] = s[u] + val;
				q.push({s[v], v});
			}
		}
	}
}
void sub1(){
    if(m < n - 1){
        cout << -1;
        return;
    }
    fo(i, 1, m){
        if(dem[{d[i].u, d[i].c}] == 1) adj[d[i].u].pb({d[i].v, 0});
        else adj[d[i].u].pb({d[i].v, d[i].val});
        if(dem[{d[i].v, d[i].c}] == 1) adj[d[i].v].pb({d[i].u, 0});
        else adj[d[i].v].pb({d[i].u, d[i].val});
    }
    fo(i, 1, n) dd[i] = false;
    dd[1] = true;
    ll ans = dfs1(1, 0);
    cout << ans;
}
void sub2(){
    if(m < n - 1){
        cout << -1;
        return;
    }
    fo(i, 1, m){
        if(dem[{d[i].u, d[i].c}] == 1) adj[d[i].u].pb({d[i].v, 0});
        else adj[d[i].u].pb({d[i].v, d[i].val});
        if(dem[{d[i].v, d[i].c}] == 1) adj[d[i].v].pb({d[i].u, 0});
        else adj[d[i].v].pb({d[i].u, d[i].val});
    }
    dijsktra(1);
    cout << s[n];
}
void solve(){
    sub2();
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    inp();
    solve();
    return 0;
}

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