Cod sursa(job #1368466)

Utilizator Consti.001FMI Dranca Constantin Consti.001 Data 2 martie 2015 17:48:00
Problema Ubuntzei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<fstream>
#include<vector>
#include<queue>
#define INF 9999999
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
struct nod
{
        int nod;
        int c;
}s;
queue <int> q;
vector <nod> l[2001];
int n,m,i,j,nec[2001],k,a[2001][2001],gr[2001];
void blm(int nod)
{
    q.push(nod);
    int st=0;
    int dr=0;
    st=1;dr=1;
    while(st<=dr)
    {
        int k=q.front();
        for(int i=0;i<l[k].size();i++)
        if(a[l[k][i].nod][gr[k]]>a[k][gr[k]]+l[k][i].c||a[l[k][i].nod][gr[k]]==0)
        {
                if(nec[l[k][i].nod]==1)
                gr[l[k][i].nod]=gr[k]+1;
                else
                gr[l[k][i].nod]=gr[k];
                a[l[k][i].nod][gr[l[k][i].nod]]=a[k][gr[k]]+l[k][i].c;
                q.push(l[k][i].nod);
                dr++;
        }
        q.pop();
        st++;
    }
    g<<a[n][gr[n]];
}
int main()
{
    f>>n>>m>>k;
    for(i=1;i<=k;i++)
    {
        int x;
        f>>x;
        nec[x]=1;
    }
    for(i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y>>s.c;
        s.nod=y;
        l[x].push_back(s);
        s.nod=x;
        l[y].push_back(s);
    }
    blm(1);
    return 0;
}