Pagini recente » Cod sursa (job #1547862) | Cod sursa (job #123327) | Cod sursa (job #2493429) | Cod sursa (job #2866305) | Cod sursa (job #2298400)
#include <fstream>
#include <queue>
#include <vector>
#include <iostream>
#include <utility>
using namespace std;
ifstream f("sate.in");
ofstream g("sate.out");
int n,m,X,Y,dist[30001];
bool viz[100001];
vector< pair<int,int> >a[30001];
void bfs(int src)
{
viz[src]=true;
queue< int >q;
q.push(src);
while(!q.empty())
{
int nod = q.front();
q.pop();
viz[nod]=true;
for(int i=0;i<a[nod].size();++i)
if(!viz[a[nod][i].first])
{
if(a[nod][i].first>nod)
dist[a[nod][i].first]=dist[nod]+a[nod][i].second;
else
dist[a[nod][i].first]=dist[nod]-a[nod][i].second;
q.push(a[nod][i].first);
}
}
}
int main()
{
f>>n>>m>>X>>Y;
for(int i=1;i<=m;++i)
{
int x,y,d;
f>>x>>y>>d;
a[x].push_back(make_pair(y,d));
a[y].push_back(make_pair(x,d));
}
bfs(X);
g<<dist[Y];
return 0;
}