【题目链接】:http://codeforces.com/problemset/problem/716/D

【题意】



给你一张图;

这张图上有一些边的权值未知;

让你确定这些权值(改成一个正整数)

使得s到t的最短路恰好为L

【题解】



首先;

算出两个值

temp1->所有的未知边的权值都为1->算出s到t的最短路;

temp2->所有的未知边的权值都为INF->算出s到t的最短路;

则必须要有

temp1<=L<=temp2

否则无解;

明白这个之后;

为每一个未知的边都标号;

标号为1..totl;

然后;

二分有多少条未知边的权值边为1;

->mid

找到最小的,使得在mid条未知边的权值为1的时候;

s到t的最短路小于L;

则第mid条边必然在s->t的最短路上;

则把那第mid条边再加上s->t的最短路与L的差值

(前Mid-1条边权值还是1);

(因为1的边越多,s到t的最短路是单调不上升的,所以这么做是可行的)

(又因为是>L和< L的边界,所以那个mid一定是在最短路上的,且没有它最短路就会大于L)



【Number Of WA】



1



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 1100;

const int M = 20000+100;

const int INF = 1e9+1;

int fir[N],nex[M],en[M],w[M],lable[M];

int totm,totl,n,m,L,s,t;

LL dis[N];

bool exsit[N];

queue <int> dl;

void add(int x,int y,int z,int flag)

{

    nex[totm] = fir[x];

    fir[x] = totm;

    en[totm] = y;

    w[totm] = z;

    if (flag) lable[totm] = totl;

    totm++;

}

LL spfa(int pre)

{

    rep1(i,1,n) dis[i] = -1;

    exsit[s] = true;

    dl.push(s);

    dis[s] = 0;

    while (!dl.empty())

    {

        int x = dl.front();

        dl.pop();

        exsit[x] = false;

        for (int i = fir[x];i>=0;i = nex[i])

        {

            int y = en[i],cost = w[i];

            if (lable[i] && lable[i]<=pre) cost = 1;

            if (lable[i] && lable[i]>pre) cost = INF;

            if (dis[y]==-1 || dis[y]>dis[x]+cost)

            {

                dis[y] = dis[x]+cost;

                if (!exsit[y])

                {

                    exsit[y] = true;

                    dl.push(y);

                }

            }

        }

    }

    return dis[t];

}

void out_graph(int key,int sp )

{

    rep1(i,1,n)

    {

        for (int j = fir[i];j >= 0;j = nex[j])

        {

            if (j&1) continue;

            cout <<i-1<<' '<<en[j]-1<<' ';

            int cost = w[j];

            if (lable[j])

            {

                if (lable[j]<key) cost = 1;

                if (lable[j]==key) cost = sp;

                if (lable[j]>key) cost = INF;

            }

            cout << cost << endl;

        }

    }

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use

    cin >> n >> m >> L >> s >> t;s++,t++;

    rep1(i,1,n) fir[i] = -1;

    rep1(i,1,m)

    {

        int x,y,z;

        cin >> x >> y >> z;

        x++,y++;

        if (z==0) totl++;

        add(x,y,z,z==0);

        add(y,x,z,z==0);

    }

    LL temp1 = spfa(totl),temp2 = spfa(0);

    if (temp1 <= L && L <=  temp2)

    {

        cout << "YES" << endl;

        int l = 0,r = totl,ans;

        LL tl,ansl;

        while (l <= r)

        {

            int mid = (l+r)>>1;

            tl = spfa(mid);

            if (tl<=L)

                ans = mid,r = mid-1,ansl = tl;

            else

                l = mid+1;

        }

        out_graph(ans,L-ansl+1);

    }

    else

        cout << "NO" << endl;

    return 0;

}