Cod sursa(job #1082645)

Utilizator StickmanLazar Alexandru Stickman Data 14 ianuarie 2014 20:41:04
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int inf=1<<30,Nmax=36001;
vector <long long int> v[Nmax];
queue <long long int> q;
long long int cost[Nmax], t[Nmax], n, m, k;
bool fort[Nmax];

void bf()
{
    int i,j,a;
    while(!q.empty())
    {
        a=q.front();
        for(i=0; i<v[a].size(); i+=2)
        {
            if(cost[v[a][i]]>=cost[a]+v[a][i+1])
            {
                if(cost[v[a][i]]==cost[a]+v[a][i+1])
                {
                    if(t[v[a][i]]>t[a])
                        t[v[a][i]]=t[a];
                    q.push(v[a][i]);

                }
                else
                {
                    q.push(v[a][i]);
                    t[v[a][i]]=t[a];
                    cost[v[a][i]]=cost[a]+v[a][i+1];
                }
            }
        }
        q.pop();
    }
}

int main()
{
    int x,y,c,i;
    ifstream in("catun.in");
    in>>n>>m>>k;
    for(i=1; i<=n; i++)
    {
        cost[i]=inf;
    }
    for(i=0; i<k; i++)
    {
        in>>c;
        q.push(c);
        fort[c]=1;
        cost[c]=0;
        t[c]=c;
    }
    for(i=0; i<m; i++)
    {
        in>>x>>y>>c;
        v[x].push_back(y);
        v[x].push_back(c);
        v[y].push_back(x);
        v[y].push_back(c);
    }
    in.close();
    bf();
    ofstream out("catun.out");
    for(i=1; i<=n; i++)
    {
        if(fort[i]) out<<0<<" ";
        else
        out<<t[i]<<" ";
    }
    out.close();
    return 0;
}