Cod sursa(job #218401)

Utilizator mariussMarius Telespan mariuss Data 1 noiembrie 2008 20:12:39
Problema PScNv Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<stdio.h>
#include<vector>
#include<algorithm>

#define mmax 500010
#define nmax 250010

using namespace std;

vector<int> v[nmax];
vector<int>cost[nmax];
int vecini[nmax];

int maximum=0;

typedef struct ev
{
    int x,y,z;
};

ev w[mmax];

int cmp(ev a1, ev b1)
{
    if(a1.z<b1.z)
        return 1;
    else return 0;
}

int aj=0;
int a,b;

void verifica (int k)
{
    for(int i=0;i<=vecini[k]-1;i++)
    {
        if(maximum<cost[k][i])
            maximum=cost[k][i];
        if(v[k][i]==4)
            aj=1;
        else verifica(v[k][i]);
    }
}


int main()
{
    int n,m,i;
    
    freopen("pscnv.in","r",stdin);
    freopen("pscnv.out","w",stdout);
    
    scanf("%d %d %d %d",&n,&m,&a,&b);
    
    for(i=1;i<=m;i++)
        scanf("%d %d %d",&w[i].x,&w[i].y,&w[i].z);
    
    sort(w+1,w+m,cmp);
    
    int val1=0,val2=0;
    
    for(i=1;i<=m;i++)
    {
        v[w[i].x].push_back(w[i].y);
        vecini[w[i].x]++;
        cost[w[i].x].push_back(w[i].z);    
                
        if(a==w[i].x)
            val1=1;
        if(b==w[i].y)
            val2=1;
        maximum=0;
        aj=0;
        if(val1 && val2)
            verifica(a);
        if(aj) break;
    }
    printf("%d",maximum);
    
    return 0;
}