Pagini recente » Cod sursa (job #2840952) | Cod sursa (job #638666) | Cod sursa (job #566339) | Cod sursa (job #2662531) | Cod sursa (job #727239)
Cod sursa(job #727239)
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
int i,j,n,m,x,y,xx,yy,cost1,d[300010],viz[3000010];
struct drum
{
int nod,cost;
};
vector<drum> a[300010];
void bf(int x)
{
int i;
queue<int> q;
q.push(x);
for(i=1;i<=n;++i)
d[i]=1<<30;
d[x]=0;
viz[x]=1;
while(!q.empty())
{
x=q.front();
for(i=0;i<a[x].size();++i)
if(!viz[a[x][i].nod])
{
d[a[x][i].nod]=d[x]+a[x][i].cost,q.push(a[x][i].nod);
viz[a[x][i].nod]=1;
}
q.pop();
}
}
int main()
{
FILE *f=fopen("sate.in","r");
FILE *g=fopen("sate.out","w");
fscanf(f,"%d%d%d%d",&n,&m,&x,&y);
for(i=1;i<=m;++i)
{
fscanf(f,"%d%d%d",&xx,&yy,&cost1);
a[xx].push_back((drum) {yy,cost1});
a[yy].push_back((drum) {xx,-cost1});
}
bf(1);
fprintf(g,"%d",d[y]-d[x]);
return 0;
}