Cod sursa(job #671526)
Utilizator | Data | 31 ianuarie 2012 17:08:00 | |
---|---|---|---|
Problema | Sate | Scor | 45 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.23 kb |
#include<fstream>
#include <iostream>
using namespace std;
int viz[300001],n,m,x,y,c[300001],k;
int cost[10000][10000],dist,final;
int vector_cost[300001];
ofstream g("sate.out");
void citire()
{
ifstream f("sate.in");
int x,y,i;
f>>n>>m>>k>>final;
int l;
for(l=1;l<=m;l++)
{
f>>x>>y>>dist;
cost[x][y]=dist;
cost[y][x]=-dist;
}
f.close();
}
void bfs(int k)
{
int li,ls,i;
li=1;
ls=1;
c[li]=k;
viz[k]=1;
while (li<=ls)
{k=c[li];
for(i=1;i<=n;i++)
if (viz[i]==0&&cost[k][i]!=0)
{ls++;
c[ls]=i;
viz[i]=1;
vector_cost[i]=vector_cost[k]+cost[k][i];;
}
li++;
}
}
int main()
{int i;
citire();
bfs(k);
g<<vector_cost[final];
g.close();
return 0;
}