一个高水准的国际性的公路赛车锦标赛即将举行。赛事规则规定，比赛要在普通的道路上举行，并且路线要有固定的长度。给定城市的地图（城市间有路相通）。 为使赛事安全举行，赛事的路线必须是单向的，可以在任何一个地方开始或结束。请你规划一下是否能安排赛程长度为S的比赛路线。
input：
首行为城市数M，路的数目N，比赛路线长度S
接下来N行为路的情况，用3个数据描述：P，Q，R；P和Q是路两端相连的城市编号。R是路的长度。所有数据都是整数，而且有以下限制：
1 <= M <= 100; 0 < N <= 10000; 1 <= S <= 1000000; 1 <= P, Q <= M; 0 < Length <= 32000。
output：
如果能安排一条所需的路线，则输出YES，否则输出NO，注意答案必需用大写字母。
input：
Sample input #1
3 2 20
1 2 10
2 3 5
Sample input #2
3 3 1000
1 2 1
2 3 1
1 3 1
output：
Sample output #1
NO
Sample output #2
YES
分析：
本题就是找出一个图中的最长的路径，和给出的S（需要的公路长度），看是否满足>=S即可。但是注意的一点是有环是一定可以的,应为有环，你走无数圈不就行了吗？ 【参考程序】：
#include<iostream>
using namespace std;
int dis[101][101],l1[101],l2[101];
int n,m,s;
bool v[101],YES;
void dfs(int x)
{
if (YES) return ;
if (v[x])
{
YES=true;
return ;
}
v[x]=true;
for (int i=1;i<=m;i++)
if (dis[x][i])
{
dis[i][x]=0;//题目要求单行，去了这边就不能去那边。
dfs(i);
int l=dis[x][i]+l1[i];
if (l>l1[x])
{
l2[x]=l1[x];l1[x]=l;
}
else if (l>l2[x]) l2[x]=l;
}
}
int main()
{
scanf("%d%d%d",&m,&n,&s);
memset(dis,0,sizeof(dis));
int x,y,c;
for (int i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&c);
if (dis[x][y])//说明有回环，有环一定可以。
{
printf("YES\n");
exit(0);
}
dis[x][y]=dis[y][x]=c;//虽然题目是单向但开始不知走那边，所以给它个双向的DFS是删去即可。
}
memset(v,false,sizeof(v));
memset(l1,0,sizeof(l1));
memset(l2,0,sizeof(l2));
YES=false;
for (int i=1;i<=m;i++)
if (!v[i]) dfs(i);
for (int i=1;i<=m;i++)
if (s<=l1[i]+l2[i])
{
YES=true;
break;
}
if (YES) printf("YES\n");
else printf("NO\n");
return 0;
}