Pagini recente » Cod sursa (job #326084) | Cod sursa (job #865745) | Cod sursa (job #1169766) | Cod sursa (job #2956066) | Cod sursa (job #2308488)
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
int n,m,x,y;
bool V[30010][30010];
vector <pair<int,int> > A[30010];
pair<int,int> p;
ifstream fin("sate.in");
ofstream fout("sate.out");
int BFS(int x, int y){
queue <pair<int,int> > q;
p.F=x;p.S=0;
q.push(p);
int pn=0,s=0,sol=-1;
while(!q.empty()){
int cn=q.front().F;
V[pn][cn]=1;
V[cn][pn]=1;
if(cn<pn)s-=q.front().S;
else s+=q.front().S;
if(cn==y){
sol=max(sol,s);
s=0;
}
for(int i=0;i<A[cn].size();i++){
if(!V[cn][A[cn][i].F])q.push(A[cn][i]);
}
if(!q.empty())q.pop();
pn=cn;
}
return sol;
}
int main(){
fin>>n>>m>>x>>y;
memset(V,0,n);
for(int i=0;i<=n;i++)A[i].clear();
for(int i=0;i<m;i++){
int xc,yc,vc;
fin>>xc>>yc>>vc;
p.F=yc;p.S=vc;
A[xc].push_back(p);
p.F=xc;
A[yc].push_back(p);
}
fout<<BFS(x,y);
return 0;
}