Cod sursa(job #1442766)

Utilizator iacovladNot Available iacovlad Data 26 mai 2015 11:01:27
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <vector>
using namespace std;
int i,j,k,m,n,t,v[30005],x,y,b,c,cost,costf;
vector <int> a[30005],pc,co[30005];
vector <int>::iterator it,itc;
int main()
{
    ifstream f("sate.in");
    ofstream g("sate.out");
    f>>n>>m>>x>>y;
    for (i=1;i<=m;i++)
      {
        f>>b>>c;
        a[b].push_back(c);
        a[c].push_back(b);
        f>>cost;
        co[b].push_back(cost);
        co[c].push_back(cost);
      };
    f.close();
    for (i=1;i<=n;i++)
        v[i]=-1;
    pc.push_back(x);
    v[x]=0;
    while (!pc.empty())
    {
        b=pc.back();
        pc.pop_back();
        for (it=a[b].begin(), itc=co[b].begin(); it!=a[b].end(); ++it, ++itc)
            if (v[*it]==-1)
            {
                if (b<*it)
                    v[*it]=v[b]+*itc;
                else
                    v[*it]=v[b]-*itc;
                pc.push_back(*it);
            }
        if (v[y]!=-1)
            break;
    }
    g<<v[y];
    g.close();
    return 0;
}