9333 | 2024. 02. 20 14:48:03 | AGergo | Hálózati átvitel | cpp17 | Hibás válasz 2/50 | 651ms | 62880 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graf; //graf[a][b] -> a b közti sebesség
//vector<bool> used; // használt-e már adott pont
vector<vector<int>> ut; // [a][b] -> K-ból a-ba menõ út b lépésben legnagyobb gyorsasága
vector<vector<int>> available; //osszes hely avoha lehet menni (adott vektorból)
int maxLepes;
void bejar(int id,int speed, int steps)
{
steps++;
if(steps <= maxLepes)
{
for(int i: available[id])
{
int spd = graf[id][i];
if(speed > spd)
{
//speed = spd;ssss
}
else
{
spd = speed;
}
if(spd > ut[i][steps])
{
ut[i][steps] = spd;
}
//cout << id << "->" << i << ": " << spd << ":" << speed << endl;
bejar(i,spd,steps);
}
}
}
int main()
{
iostream::sync_with_stdio(0);cin.tie(0);
//dijkstra csak minden utat eltárolsz
int csomo,vonal,koz;
cin >> csomo >> vonal >> koz >> maxLepes;
graf.resize(csomo+1,vector<int>(csomo+1));
available.resize(csomo+1);
int p1,p2,v;
for(int i = 0; i < vonal; i++)
{
cin >> p1 >> p2 >> v;
graf[p1][p2] = v;
graf[p2][p1] = v;
available[p1].resize(available[p1].size()+1);
available[p1][available[p1].size()-1] = p2;
available[p2].resize(available[p2].size()+1);
available[p2][available[p2].size()-1] = p1;
}
//used.resize(csomo+1,false);
ut.resize(csomo+1,vector<int>(maxLepes+1,-1));
bejar(koz,100001,0);
int highest;
//cout << "-----------------------\n";
for(int i = 1;i <= csomo;i++)
{
if(i == koz)
{
cout << "0\n";
}
else
{
highest = 0;
for(int x: ut[i])
{
//cout << x << ":";
if( x > highest )
{
highest = x;
}
}
cout << highest <<"\n";
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 2/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 123ms | 2400 KiB | |||
3 | Hibás válasz | 0/1 | 3ms | 2232 KiB | |||
4 | Hibás válasz | 0/1 | 3ms | 2436 KiB | |||
5 | Elfogadva | 2/2 | 370ms | 2732 KiB | |||
6 | Időlimit túllépés | 0/2 | 570ms | 2012 KiB | |||
7 | Időlimit túllépés | 0/2 | 638ms | 3260 KiB | |||
8 | Időlimit túllépés | 0/2 | 561ms | 3340 KiB | |||
9 | Időlimit túllépés | 0/1 | 561ms | 6768 KiB | |||
10 | Időlimit túllépés | 0/1 | 555ms | 6864 KiB | |||
11 | Időlimit túllépés | 0/1 | 565ms | 7364 KiB | |||
12 | Időlimit túllépés | 0/1 | 566ms | 7600 KiB | |||
13 | Időlimit túllépés | 0/2 | 570ms | 7748 KiB | |||
14 | Időlimit túllépés | 0/2 | 555ms | 7788 KiB | |||
15 | Időlimit túllépés | 0/2 | 565ms | 8000 KiB | |||
16 | Időlimit túllépés | 0/2 | 555ms | 7948 KiB | |||
17 | Időlimit túllépés | 0/2 | 651ms | 8116 KiB | |||
18 | Időlimit túllépés | 0/2 | 574ms | 8604 KiB | |||
19 | Időlimit túllépés | 0/2 | 563ms | 8756 KiB | |||
20 | Időlimit túllépés | 0/2 | 570ms | 8732 KiB | |||
21 | Futási hiba | 0/1 | 26ms | 62880 KiB | |||
22 | Futási hiba | 0/1 | 28ms | 62640 KiB | |||
23 | Futási hiba | 0/1 | 34ms | 62596 KiB | |||
24 | Futási hiba | 0/1 | 32ms | 62504 KiB | |||
25 | Futási hiba | 0/2 | 28ms | 62492 KiB | |||
26 | Futási hiba | 0/2 | 32ms | 62460 KiB | |||
27 | Futási hiba | 0/2 | 32ms | 62320 KiB | |||
28 | Futási hiba | 0/2 | 29ms | 62312 KiB | |||
29 | Futási hiba | 0/2 | 28ms | 62080 KiB | |||
30 | Futási hiba | 0/2 | 29ms | 62076 KiB | |||
31 | Futási hiba | 0/2 | 32ms | 62052 KiB | |||
32 | Futási hiba | 0/2 | 29ms | 62024 KiB |