Cod sursa(job #1489647)

Utilizator elevenstrArina Raileanu elevenstr Data 21 septembrie 2015 19:58:57
Problema Sate Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream in("sate.in");
ofstream out("sate.out");
#define MAX 16000
queue <long long int> Q;
vector <long long int > v[MAX];
long long int d[MAX];
long long int dist[MAX][MAX];

int main()
{ long long int n,m,x,y,i,a,b,xs,dr,f;

    in>>n>>m>>x>>y;
    for(i=1;i<=m;i++)
      {   in>>a>>b>>dr;
          v[a].push_back(b);
          v[b].push_back(a);
          dist[a][b]=dr;
          dist[b][a]=dr;
      }
    d[x]=1;
    Q.push(x);
    while(!Q.empty())
    { f=Q.front();
    Q.pop();
    for(vector <long long int > ::iterator it=v[f].begin();it!=v[f].end();it++)
    {
        if(d[*it]==0)
        {
            if(*it>f)d[*it]=d[f]+dist[f][*it];
            else d[*it]=d[f]-dist[f][*it];
         Q.push(*it);
          }
       }

    }
    out<<d[y]-1;

    return 0;
}