Submission #1169657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169657		username_____here	Construction Project 2 (JOI24_ho_t2)	C++20	0 / 100	2092 ms	740 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> veci;
typedef vector<ll> vecll;
#define fi first
#define se second
#define vec vector
#define pq priority_queue

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll n, m;
    cin >> n >> m;
    ll s, t, l, k;
    cin >> s >> t >> l >> k;
    s--; t--;
    vec<pll> adj[n];
    while (m--) {
        ll x, y, c;
        cin >> x >> y >> c;
        x--; y--;
        adj[x].push_back({y, c});
        adj[y].push_back({x, c});
    }
    ll ans=0;
    for (ll i1=0; i1<n; i1++) {
        for (ll j1=i1+1; j1<n; j1++) {
            adj[j1].push_back({i1, l});
            adj[i1].push_back({j1, l});
            ll dist[n];
            priority_queue<pll,vector<pll>,greater<pll>> q;
            //change 2nd val for changing start
            q.push(pll(0,s));
            for (int i = 0; i < n; i++){
                dist[i] = 1000000000;
            }//  |
            //   V change this val for changing start
            dist[s] = 0;
            while (!q.empty()){
                pll p = q.top();
                q.pop();
                ll d = p.first, u = p.second;
                if (d > dist[u]) continue;
                for (ll i = 0; i < (adj[u]).size(); i++){
                    ll nu = adj[u][i].first,w = adj[u][i].second;
                    if (dist[nu] > dist[u] + w){
                        dist[nu] = dist[u] + w;
                        q.push(pll(dist[nu],nu));
                    }
                }
            }
            ans += (dist[t]<=k);
            adj[j1].pop_back();
            adj[i1].pop_back();
        }
    }
    cout << ans;
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 16
• Subtask 3: 0 / 29
• Subtask 4: 0 / 47