Cod sursa(job #2039821)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 14 octombrie 2017 23:18:19
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <cstdio>
#include <vector>
#include <climits>
using namespace std;
const int nmax=3e5+3;
long long t,n,m,s,d,k,a,b,timp,v[nmax][4],nr,c;
long long dist[nmax],suma;
vector <int> sol;
void init()
{
    for(int i=1;i<=n;++i) dist[i]=INT_MAX;
    dist[d]=0;
}
void read()
{
    scanf("%d%d%d%d",&n,&m,&s,&d);
    init();
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&v[i][1],&v[i][2],&v[i][3]);
        if(v[i][1]==d) dist[v[i][2]]=v[i][3];
        if(v[i][2]==d) dist[v[i][1]]=v[i][3];
    }
    scanf("%d",&k);
    for(int i=1;i<=k;++i)
    {
        scanf("%d",&a);
        suma+=v[a][3];
    }
}
void dijkstra()
{
    bool ok=1;
    while(ok&&nr<n)
    {
        ok=0;
        for(int i=1;i<=m;++i)
        {
            a=v[i][1];
            b=v[i][2];
            c=v[i][3];
            if(dist[a]>dist[b]+c)
            {
                dist[a]=dist[b]+c;
                ok=1;
            }
            if(dist[b]>dist[a]+c)
            {
                dist[b]=dist[a]+c;
                ok=1;
            }
        }
        ++nr;
    }
}
void solve()
{
    for(int i=1;i<=n;++i)
    {
        if(dist[i]<=suma) sol.push_back(i);
    }
    printf("%d\n",sol.size());
    for(int i=0;i<sol.size();++i) printf("%d ",sol[i]);
    printf("\n");
}
int main()
{
    freopen("tempest.in","r",stdin);
    freopen("tempest.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        suma=nr=0;
        read();
        sol.clear();
        dijkstra();
        solve();
    }
    return 0;
}