8080 2024. 01. 12 12:17:25 Huni136 Hálózati átvitel cpp17 Elfogadva 50/50 61ms 6196 KiB 
#include <iostream>
#include <vector>
using namespace std;
int n,h,kezd;
vector<vector<pair<int,int>>> vc(10001);
//vector<int> tav(10001,1e9);

void bellmanford()
{
    vector<int> tav1(n+1,-1);
    vector<int> tav2(n+1,-1);
    tav1[kezd]=1e9;
    tav2[kezd]=1e9;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(auto it: vc[j])
            {
                // tav[it.first]=min(tav[it.first],it.second);
                if(tav1[it.first]<min(it.second,tav2[j]))
                {
                    tav1[it.first]=min(it.second,tav2[j]);
                }
            }
        }
        tav2=tav1;
    }
    tav1[kezd]=0;
    for(int i=1;i<=n;i++)
    {
        cout<<(tav1[i]!=-1?tav1[i]:-1)<<endl;
    }
}

int main()
{
    int m, k;
    cin>>n>>m>>kezd>>h;
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        vc[x].emplace_back(y,z);
        vc[y].emplace_back(x,z);
    }

    bellmanford();

    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 2064 KiB
2 Elfogadva 0/0 3ms 2340 KiB
3 Elfogadva 1/1 3ms 2476 KiB
4 Elfogadva 1/1 3ms 2564 KiB
5 Elfogadva 2/2 3ms 2688 KiB
6 Elfogadva 2/2 3ms 2920 KiB
7 Elfogadva 2/2 4ms 3280 KiB
8 Elfogadva 2/2 4ms 3224 KiB
9 Elfogadva 1/1 4ms 3240 KiB
10 Elfogadva 1/1 6ms 3256 KiB
11 Elfogadva 1/1 8ms 3764 KiB
12 Elfogadva 1/1 8ms 3848 KiB
13 Elfogadva 2/2 8ms 3848 KiB
14 Elfogadva 2/2 9ms 3976 KiB
15 Elfogadva 2/2 14ms 4080 KiB
16 Elfogadva 2/2 14ms 4076 KiB
17 Elfogadva 2/2 14ms 4312 KiB
18 Elfogadva 2/2 14ms 4228 KiB
19 Elfogadva 2/2 14ms 4336 KiB
20 Elfogadva 2/2 14ms 4336 KiB
21 Elfogadva 1/1 35ms 4616 KiB
22 Elfogadva 1/1 48ms 4872 KiB
23 Elfogadva 1/1 43ms 4992 KiB
24 Elfogadva 1/1 50ms 5520 KiB
25 Elfogadva 2/2 57ms 5572 KiB
26 Elfogadva 2/2 61ms 5716 KiB
27 Elfogadva 2/2 57ms 5784 KiB
28 Elfogadva 2/2 39ms 5928 KiB
29 Elfogadva 2/2 41ms 5860 KiB
30 Elfogadva 2/2 39ms 6040 KiB
31 Elfogadva 2/2 39ms 6084 KiB
32 Elfogadva 2/2 41ms 6196 KiB