Description
一个n个点m条边的无向图，每条边有正边权，0边权表示可以修改该条边的边权为任意正整数，给出起点s和终点t，问是否有一种修改边权的方案使得s到t的最短路为L
Input
第一行五个整数n,m,L,s,t分别表示点数，边数，要求的最短路的长度，起点和终点，之后m行每行三个整数u,v,c表示u和v之间有一条权值为c的边，如果c=0表示该条边的边权可以被修改(2<=n<=1000,1<=m<=10000,1<=L<=1e9,0<=s,t<=n-1,s!=t)
Output
如果存在一个满足条件的方案则输出YES以及每条边的边权，否则输出NO
Sample Input
5 5 13 0 4
0 1 5
2 1 2
3 2 3
1 4 0
4 3 4
Sample Output
YES
0 1 5
2 1 2
3 2 3
1 4 8
4 3 4
Solution
首先对除去可修改边的图以s为起点跑一遍最短路，如果dis[t] < L，说明不论如何修改可修改边的边权，最终dis[t]必然小于L，无解；如果dis[t]>=L，则一条条的加入可修改边看是否可以缩短s到t的最短路，因为边权必须是正整数，所以初始边权设为最小值1，跑完最短路后如果dis[t] < L，那么说明该条边在最短路径上，那么把该条边边权设为L-(dis[t]-1)就可以使dis[t]变成L了，在处理完所有的可修改边后，如果dis[t]还是大于L则无解，否则有解
Code
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
#define maxn 1111
#define maxm 11111
typedef pair<int,int>P;//first是最短距离,second是顶点编号
struct edge
{
int to,cost;
};
int n,m,L,s,t;
vector<edge>g[maxn];//邻接矩阵
ll dis[maxn];//dis[i]表示i到s的最短距离
void init(int n)//初始化
{
for(int i=0;i<n;i++)g[i].clear();
}
void add(int u,int v,int c)//单向边,从u到v,权值为c
{
g[u].push_back((edge){v,c});
}
void Dijkstra(int s)//求所有顶点到起点s的最短距离
{
priority_queue< P,vector<P>,greater<P> >que;//堆按照first从大到小的顺序取出值
for(int i=0;i<n;i++)dis[i]=1e18;
dis[s]=0;
que.push(P(0,s));//起点进队
while(!que.empty())
{
P p=que.top();
que.pop();
int v=p.second;
if(dis[v]<p.first) continue;//剪枝
for(int i=0;i<g[v].size();i++)
{
edge e=g[v][i];
if(dis[e.to]>dis[v]+e.cost)
{
dis[e.to]=dis[v]+e.cost;
que.push(P(dis[e.to],e.to));
}
}
}
}
int e[maxm][3];
int main()
{
scanf("%d%d%d%d%d",&n,&m,&L,&s,&t);
init(n);
for(int i=0;i<m;i++)
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
if(c)add(u,v,c),add(v,u,c);
e[i][0]=u,e[i][1]=v,e[i][2]=c;
}
Dijkstra(s);
if(dis[t]<L)printf("NO\n");
else
{
for(int i=0;i<m;i++)
{
int u=e[i][0],v=e[i][1],c=e[i][2];
if(c)continue;
add(u,v,1),add(v,u,1);
e[i][2]=1;
Dijkstra(s);
if(dis[t]<L)
{
e[i][2]=L-dis[t]+1;
g[u][g[u].size()-1].cost=e[i][2];
g[v][g[v].size()-1].cost=e[i][2];
}
}
if(dis[t]>L)printf("NO\n");
else
{
printf("YES\n");
for(int i=0;i<m;i++)printf("%d %d %d\n",e[i][0],e[i][1],e[i][2]);
}
}
return 0;
}