# |
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 |
|
/*
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();
}
Click to see test details