Cod sursa(job #900318)

Utilizator robert.onesimRobert Onesim robert.onesim Data 28 februarie 2013 19:04:08
Problema Sate Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#include <queue>
#include <vector>
#define NMAX 30002
using namespace std;
ifstream fin("sate.in");
ofstream fout("sate.out");
void bfs();
void citire();
struct muchie{int vf,cost;};
vector <muchie> L[NMAX];
queue <int> C;
int dmin[NMAX],viz[NMAX],s,f,n,m;
int main()
{
    citire();
    bfs();
}
void citire()
{
    int i,c,x,y;
    muchie aux;
    fin>>n>>m>>s>>f;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        aux.vf=y;aux.cost=c;
        L[x].push_back(aux);
        aux.vf=x;
        L[y].push_back(aux);
    }
}
void bfs()
{
    int i,j,vfmin;
    viz[s]=1;
    for(i=0;i<L[s].size();i++)
    {
        dmin[L[s][i].vf]=L[s][i].cost;  C.push(L[s][i].vf);
        viz[L[s][i].vf]=1;
    }
    dmin[s]=0;
    while(!C.empty())
    {
        vfmin=C.front();
        C.pop();
        for(j=0;j<L[vfmin].size();j++)
        {
            if(L[vfmin][j].vf>vfmin) dmin[L[vfmin][j].vf]=dmin[vfmin]+L[vfmin][j].cost;
            else dmin[L[vfmin][j].vf]=dmin[vfmin]-L[vfmin][j].cost;
            if(viz[L[vfmin][j].vf]==0)
            {
                C.push(L[vfmin][j].vf);
                viz[L[vfmin][j].vf]=1;
            }
        }
     }
     if(dmin[f]==0) fout<<-1;
     else
         fout<<dmin[f];
}