Submission #1123067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123067		ro9669	Construction Project 2 (JOI24_ho_t2)	C++17	16 / 100	2095 ms	5352 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(2e5)+7;

int n , m , s , t , l; ll k;
vector<ii> g[maxN];
ll d[maxN];

void dijkstra(){
    for (int i = 1 ; i <= n ; i++) d[i] = k + 1;
    d[s] = 0;
    priority_queue<lli , vector<lli> , greater<lli>> pq;
    pq.push({d[s] , s});
    while (pq.empty() == 0){
        auto it = pq.top(); pq.pop();
        int u = it.se;
        if (d[u] != it.fi) continue;
        for (auto e : g[u]){
            int v = e.fi;
            int w = e.se;
            if (d[v] > it.fi + 1ll * w){
                d[v] = it.fi + 1ll * w;
                pq.push({d[v] , v});
            }
        }
    }
}

void solve(){
    cin >> n >> m >> s >> t >> l >> k;
    for (int i = 1 ; i <= m ; i++){
        int u , v , w;
        cin >> u >> v >> w;
        g[u].push_back({v , w});
        g[v].push_back({u , w});
    }
    int ans = 0;
    for (int u = 1 ; u <= n ; u++){
        for (int v = u + 1 ; v <= n ; v++){
            g[u].push_back({v , l});
            g[v].push_back({u , l});
            dijkstra();
            if (d[t] <= k) ans++;
            g[u].pop_back();
            g[v].pop_back();
        }
    }
    cout << ans << "\n";
}

#define name "A"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(name".INP" , "r")){
        freopen(name".INP" , "r" , stdin);
        freopen(name".OUT" , "w" , stdout);
    }
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(name".INP" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(name".OUT" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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