7427 | 2024. 01. 08 20:46:55 | horvathabel | Villanyautó | cpp17 | Hibás válasz 9/60 | 277ms | 4200 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll mx=100000000000;
vector<pair<ll,ll>> g[101];
bool dijkstra(ll mxut, ll k, ll x, ll n){
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> q;
vector<ll> maxk;
maxk.resize(n+1,0);
q.push({0,x});
vector<ll>t;
t.resize(101, mx);
t[x]=0;
while (!q.empty()){
auto v=q.top();
q.pop();
for (auto edge:g[v.second]){
bool van=false;
if (t[edge.first]>edge.second+v.first){
if (edge.second+v.first>mxut){
if (edge.second<=mxut){;
t[edge.first]=edge.second;
maxk[edge.first]=max(maxk[edge.first], maxk[v.second]+1);
van=true;
}
}
else{
t[edge.first]=edge.second+v.first;
van=true;
}
if (van) q.push({t[edge.first],edge.first});
}
}
}
for (ll i=1; i<=n;i++) if (maxk[i]>k || t[i]==mx) return false;
return true;
}
int main()
{
ll n,m,k;
cin>>n>>m>>k;
ll r=0;
for (ll i=0; i<m;i++){
ll a, b,c;
cin>>a>>b>>c;
r+=c;
g[a].push_back({b,c});
g[b].push_back({a,c});
}
ll l=0;
while (l+1!=r){
ll m=(l+r)/2;
bool good=true;
for (ll i=1; i<=n;i++){
good=dijkstra(m, k, i, n);
}
if (good) r=m;
else l=m;
}
cout<<l+1<<endl;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 9/60 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1816 KiB | |||
2 | Elfogadva | 0/0 | 107ms | 2268 KiB | |||
3 | Hibás válasz | 0/1 | 18ms | 2256 KiB | |||
4 | Hibás válasz | 0/1 | 39ms | 2668 KiB | |||
5 | Hibás válasz | 0/1 | 48ms | 2632 KiB | |||
6 | Hibás válasz | 0/2 | 79ms | 3000 KiB | |||
7 | Hibás válasz | 0/2 | 166ms | 3132 KiB | |||
8 | Hibás válasz | 0/2 | 277ms | 3468 KiB | |||
9 | Elfogadva | 1/1 | 4ms | 3100 KiB | |||
10 | Hibás válasz | 0/1 | 4ms | 3100 KiB | |||
11 | Hibás válasz | 0/1 | 4ms | 3236 KiB | |||
12 | Hibás válasz | 0/2 | 12ms | 3480 KiB | |||
13 | Hibás válasz | 0/2 | 9ms | 3356 KiB | |||
14 | Hibás válasz | 0/2 | 6ms | 3428 KiB | |||
15 | Hibás válasz | 0/3 | 9ms | 3536 KiB | |||
16 | Hibás válasz | 0/3 | 14ms | 3640 KiB | |||
17 | Hibás válasz | 0/2 | 14ms | 3524 KiB | |||
18 | Hibás válasz | 0/2 | 35ms | 3660 KiB | |||
19 | Hibás válasz | 0/2 | 35ms | 3900 KiB | |||
20 | Hibás válasz | 0/2 | 48ms | 3836 KiB | |||
21 | Elfogadva | 2/2 | 28ms | 3812 KiB | |||
22 | Hibás válasz | 0/2 | 8ms | 3768 KiB | |||
23 | Hibás válasz | 0/3 | 48ms | 3888 KiB | |||
24 | Hibás válasz | 0/3 | 133ms | 3956 KiB | |||
25 | Hibás válasz | 0/3 | 136ms | 3852 KiB | |||
26 | Hibás válasz | 0/3 | 210ms | 4168 KiB | |||
27 | Elfogadva | 3/3 | 115ms | 4200 KiB | |||
28 | Hibás válasz | 0/3 | 48ms | 3996 KiB | |||
29 | Hibás válasz | 0/3 | 45ms | 4144 KiB | |||
30 | Elfogadva | 3/3 | 52ms | 4116 KiB |