Codeforces Round #372 (Div. 1)B Complete The Graph（最短路+贪心）

B. Complete The Graph

time limit per test: 4 seconds
memory limit per test: 256 megabytes

ZS the Coder has drawn an undirected graph of n vertices numbered from 0 to n - 1 and m edges between them. Each edge of the graph is weighted, each weight is a positive integer.

The next day, ZS the Coder realized that some of the weights were erased! So he wants to reassign positive integer weight to each of the edges which weights were erased, so that the length of the shortest path between vertices s and t in the resulting graph is exactly L. Can you help him?

Input

The first line contains five integers n, m, L, s, t ($2 ≤ n≤ 1000, 1 ≤ m ≤ 10 000, 1 ≤ L ≤ 10^9, 0 ≤ s, t ≤ n- 1, s ≠ t$) — the number of vertices, number of edges, the desired length of shortest path, starting vertex and ending vertex respectively.

Then, m lines describing the edges of the graph follow. i-th of them contains three integers, $u_i, v_i, w_i(0 ≤ u_i, v_i ≤ n - 1, u_i ≠ v_i, 0 ≤ w_i ≤ 10^9). u_i and v_i$ denote the endpoints of the edge and $w_i$ denotes its weight. If $w_i$ is equal to 0 then the weight of the corresponding edge was erased.

It is guaranteed that there is at most one edge between any pair of vertices.

Output

Print "NO" (without quotes) in the only line if it's not possible to assign the weights in a required way.

Otherwise, print "YES" in the first line. Next m lines should contain the edges of the resulting graph, with weights assigned to edges which weights were erased. i-th of them should contain three integers $u_i, v_i \ and \ w_i$, denoting an edge between vertices $u_i$ and $v_i$ of weight $w_i$. The edges of the new graph must coincide with the ones in the graph from the input. The weights that were not erased must remain unchanged whereas the new weights can be any positive integer not exceeding $10^{18}$.

The order of the edges in the output doesn't matter. The length of the shortest path between s and t must be equal to L.

If there are multiple solutions, print any of them.

Examples

2 1 123456789 0 1
0 1 0

YES
0 1 123456789

2 1 999999999 1 0
0 1 1000000000

NO

Note

Here's how the graph in the first sample case looks like :

In the first sample case, there is only one missing edge weight. Placing the weight of 8 gives a shortest path from 0 to 4 of length 13.

In the second sample case, there is only a single edge. Clearly, the only way is to replace the missing weight with 123456789.

In the last sample case, there is no weights to assign but the length of the shortest path doesn't match the required value, so the answer is "NO".

链接

http://codeforces.com/contest/715/problem/B

题意

n个点m条边的无向带权图，最开始有一些边的权值为0（零边），问能够通过修改零边的权值（一个正整数）使得从s出发到达t的最短路为L。如果能，输出每条边的权值（一组方案即可），不能则输出NO。

题解

我们先考虑不加零边时s到t的最短路径d。

如果d小于L，那么肯定无法通过修改零边的权值使得最短路为L，因为加边之后的最短路只会小于等于d。
如果d等于L，那么直接把零边修改为无穷大（即不可到达）就行。
如果d大于L，那么此时贪心的修改零边的权值为1，每次修改一条零边，如果出现最短路径d<=L那么当前边一定是目前状态下最短路中的边，可以修改当前边的权值为L-d+1，剩余边的权值为无穷大，那么久找到了符合要求的一组解。

好像也可以通过二分来做，二分所有零边的权值。

代码

Status	Accepted
Time	670ms
Memory	1696kB
Length	3217

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
const int maxm = 10010;
int n, m, L;

struct qnode
{
    int v, c;
    qnode () {}
    qnode (int _v, int _c): v(_v), c(_c) {}
    bool operator < (const qnode & r) const
    {
        return c > r.c;
    }
};

struct Edge
{
    int to, cost;
    Edge (int _to, int _cost): to(_to), cost(_cost) {}
};

vector <Edge> E[maxn<<2];
bool vis[maxn];
int dist[maxn];

void addedge(int u, int v, int w)
{
    E[u].push_back(Edge(v, w));
}

int dijkstra(int s, int t)
{
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i <= n; ++i)
        dist[i] = inf;
    priority_queue <qnode> que;
    dist[s] = 0;
    que.push(qnode(s, 0));
    qnode tmp;
    while (!que.empty())
    {
        tmp = que.top();
        que.pop();
        int u = tmp.v;
        if (u == t) // 到达t返回最短路径
            return tmp.c;
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < E[u].size(); ++i)
        {
            int v = E[u][i].to, cost = E[u][i].cost;
            if (!vis[v] && dist[v] > dist[u] + cost)
            {
                dist[v] = dist[u] + cost;
                que.push(qnode(v, dist[v]));
            }
        }
    }
    return inf; // 最短路径不存在/大于L
}

struct edge // 保存边
{
    int u, v, w;
}e[maxm << 1], e0[maxm<<1];

int main()
{
    int u, v, w, s, t;
    scanf("%d%d%d%d%d", &n, &m, &L, &s, &t);
    int tot1 = 0, tot2 = 0; // 有权值的边数，权值为0边数
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d%d", &u, &v, &w);
        if (w != 0)
        {
            addedge(u, v, w);
            addedge(v, u, w);
            e[tot1].u = u, e[tot1].v = v, e[tot1++].w = w; // 权值边
        }
        else
            e0[tot2].u = u, e0[tot2].v = v, e0[tot2++].w = w; // 零边
    }
    int ans = dijkstra(s, t);
    if (ans < L) // 不加零边时的最短路小于L，说明无法通过加边符合要求
        printf("NO\n");
    else if (ans == L) // 不加零边时的最短路等于L，将零边设置为无穷大即不可到达即可
    {
        printf("YES\n");
        for (int i = 0; i < tot1; ++i)
            printf("%d %d %d\n", e[i].u, e[i].v, e[i].w);
        for (int i = 0; i < tot2; ++i)
            printf("%d %d %d\n", e0[i].u, e0[i].v, inf);
    }
    else
    {
        int flag = -1;
        for (int i = 0; i < tot2; ++i)
        {
            addedge(e0[i].u, e0[i].v, 1);
            addedge(e0[i].v, e0[i].u, 1);
            ans = dijkstra(s, t);
            if (ans > L)
                continue;
            flag = i; // 加了这条边后使得最短路小于等于L，说明该边一定为最短路上的边
            break;
        }
        if (flag == -1)
            printf("NO\n");
        else
        {
            printf("YES\n");
            for (int i = 0; i < tot1; ++i)
                printf("%d %d %d\n", e[i].u, e[i].v, e[i].w);
            for (int i = 0; i < flag; ++i) // flag之前的边权为1
                printf("%d %d %d\n", e0[i].u, e0[i].v, 1);  // flag边权为L-ans+1
            printf("%d %d %d\n", e0[flag].u, e0[flag].v, L - ans + 1);
            for (int i = flag + 1; i < tot2; ++i) // 其余边设为无穷大
                printf("%d %d %d\n", e0[i].u, e0[i].v, inf);
        }
    }
    return 0;
}

这道题鸽了好久了...终于过了。

The end.
2018-08-19 星期日