General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
55517344 Practice:
luismo
715B - 87 GNU C++11 Wrong answer on test 16 31 ms 9016 KB 2019-06-13 09:17:01 2019-06-13 09:17:01
→ Source
/*
	Author: Luis Manuel D�az Bar�n (LUISMO)
	Problem:
	Online Judge:
	Idea:
*/
#include<bits/stdc++.h>
// Types
#define ll long long
#define ull unsigned long long
// IO
#define sf scanf
#define pf printf
#define mkp make_pair
#define fi first
#define se second
#define endl "\n"

using namespace std;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll inf = 1e18 + 3;
const int mod = 1e9 + 7;
const int lim = 1e3 + 2;


int n, m, s, t;
ll L;

ll mt[lim][lim];
bool special[lim][lim];


ll di[lim];
int pi[lim];
bool taken[lim];

void ISS()
{
    for(int i = 0; i <= n; i++)
    {
        di[i] = inf;
        pi[i] = -1;
        taken[i] = false;
    }
}

void Dijkstra(int s)
{
    // ISS
    ISS();

    di[s] = 0;
    int idx = s;
    while(idx != -1)
    {
        taken[idx] = true;
        // for each adjacent node -> relax
        for(int i = 0; i < n; i++)
        {
            if(mt[idx][i] > 0)
            {
                if(di[idx] + mt[idx][i] < di[i])
                {
                    di[i] = di[idx] + mt[idx][i];
                    pi[i] = idx;
                }
            }
        }

        idx = -1;
        ll mnDis = inf;
        for(int i = 0; i < n; i++)
        {
            if(!taken[i] && di[i] < mnDis)
            {
                idx = i;
                mnDis = di[i];
            }
        }
    }
}

void solve()
{
    cin >> n >> m >> L >> s >> t;
    // reading edges
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        mt[a][b] = mt[b][a] = c;
        if(c == 0)
        {
            special[a][b] = special[b][a] = true;
            // mt[a][b] = mt[b][a] = 1;
        }
    }

    Dijkstra(s);
    //cout << di[t] << endl;

    if(di[t] < L)
    {
        cout << "NO";
        return;
    }

    // set edges in zero to one
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(special[i][j])
                mt[i][j] = mt[j][i] = 1;

    Dijkstra(s);
    //cout << di[t] << endl;

    if(L < di[t])
    {
        cout << "NO";
        return;
    }

    int k = t;
    ll auxL = L;
    while(pi[k] != -1)
    {
        if(special[k][pi[k]])
        {
            mt[k][pi[k]] = mt[pi[k]][k] += auxL - di[t];
            special[k][pi[k]] = special[pi[k]][k] = false;;;
            auxL = di[t];
        }
        k = pi[k];
    }

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(special[i][j])
            {
                mt[i][j] = mt[j][i] = 1e16;
            }


    cout << "YES" << endl;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(mt[i][j])
            {
                cout << i << " " << j << " " << mt[i][j] << endl;
                mt[j][i] = 0;
            }
}

void fastIO()
{
	cin.sync_with_stdio(false);
	cin.tie(0);
}

void IO()
{
	if(fopen("d:\\lmo.in","r") != NULL)
	{
		freopen("d:\\lmo.in","r",stdin);

	}
	else if(fopen("/media/Beijing/lmo.in","r") != NULL)
	{
		freopen("/media/Beijing/lmo.in", "r", stdin);
	}
}

int main()
{
	IO();

	fastIO();

	solve();
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details