Pagini recente » Cod sursa (job #994709) | Cod sursa (job #1132721) | Cod sursa (job #877809)
Cod sursa(job #877809)
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
ifstream f("sate.in");
ofstream g("sate.out");
int a,b,c,n,m,x,y,i,d[30010];
struct nod{int x,cost;};
nod v;
vector<nod>l[30010];
queue<int>q;
int main()
{
f>>n>>m>>x>>y;
for(i=1;i<=m;++i)
{
f>>a>>b>>c;
v.x=b;
v.cost=c;
l[a].push_back(v);
v.x=a;
v.cost=-c;
l[b].push_back(v);
}
memset(d,-1,sizeof(d));
d[x]=0;
q.push(x);
while(!q.empty())
{
x=q.front();
for(vector<nod>::iterator it=l[x].begin();it!=l[x].end();++it)
{
v=*it;
if(d[v.x]==-1)
{
d[v.x]=d[x]+v.cost;
q.push(v.x);
}
}
q.pop();
}
g<<d[y]<<'\n';
return 0;
}