Cod sursa(job #2373459)

Utilizator munteanue28no one munteanue28 Data 7 martie 2019 13:38:53
Problema Sate Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>
#define maxn 22000
using namespace std;
 
ifstream fi ("sate.in");
ofstream fo ("sate.out");


int m,n,X,Y,q[30002],a[maxn][maxn];


void BFS (int y)
{
	 while(q[y] == 0)
    {
        for(int i = 1;i <= n; ++i)
            {
            	for (int j = 1; j <= n; ++j)
				{
            		if(q[i] != 0  &&  a[i][j] != 0 && q[j] == 0)
                	{
                    	q[j]=q[i]+a[i][j];
                	}
            		else
                		if(q[i]==0 && a[i][j] != 0 && q[j] !=0 )
                    	{
                        	q[i]=q[j]-a[i][j];
                    	}
            	}
    		} 
	}
}


int main () 
{
		int x,y,d;
		
		fi >> n >> m >> X >> Y; 
		
		memset (a,0,sizeof(a));
		
		while (m--)
		{
			fi >> x >> y >>d;
			a[x][y]=d;
			a[y][x]=d;
		}
		
		
		q[X]=1;
		
		BFS (Y);
		
		fo<<q[Y]-1;
	
	return 0;
}