http://acm.timus.ru/problem.aspx?space=1&num=1227标明出处 ： roba
题目大意：要举办一场汽车拉力赛，赛道的长度S给定，每条公路的信息给定（公路的起点城市、终点城市、长度）。赛道的起点和终点可以设在公路的任何位置（不一定要恰好在城市），但为了安全起见，赛道只能设为单向的。问能否找到一条长度为S的赛道。
城市数M<=100, 公路数N<=10000
分析 ： 如果有环，必成立，如果无环，则找树的直径(我有文章介绍也是roba的资料)
代码 ：
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int N = 101;
int color[N], n, m, s, map[N][N], d[N], aaaa[N][N];
bool judge[N], circle;
void dfs(int v){ //判环
int i, t;judge[v] = true;
//printf("dfs : %d\n", v);
if(!circle){
for(i = 1; i <= n; i++){
if(map[v][i]){
if(!judge[i]){
t = map[v][i];
map[v][i] = map[i][v]= 0;
dfs(i);
map[v][i] = map[i][v] = t;
}
else{
if(i != v)circle = true;
}
}
}
}
}
queue<int> qu, qq;
void bfs(int s){
int i, j, w, t, si;
qu = qq;qu.push(s);judge[s] = true;d[s] = 0;
while(true){
si = qu.size();
if(!si)return;
t = qu.front();qu.pop();
for(i = 1; i <= n; i++){
if(map[t][i] && !judge[i]){
judge[i] = true;
d[i] = d[t] + map[t][i];qu.push(i);
}
}
}
}
int main(){
freopen("1227.in", "r", stdin);
freopen("1227.out", "w", stdout);
int i, j, u, v, w;bool ok, bo;
while(scanf("%d%d%d", &n, &m, &s) != -1){
memset(judge, 0, sizeof(judge));
memset(map, 0, sizeof(map));
memset(aaaa, 0, sizeof(aaaa));
circle = ok = false;
for(i = 0; i < m; i++){
scanf("%d%d%d", &u, &v, &w);
if(u == v)ok = true;
map[u][v] = map[v][u] = w;
aaaa[u][v] = ++aaaa[v][u];
if(aaaa[u][v] >= 2)ok = true;
}
if(ok){puts("YES");continue;}
else{
for(i = 1; i <= n; i++)if(!circle && !judge[i])dfs(i);//有可能整个图不联通
//puts("
");
if(circle)puts("YES");
else{
memset(judge, 0, sizeof(judge));
for(i = 1; i <= n; i++)if(!judge[i])bfs(i);w = -1;//有可能整个图不联通
for(i = 1; i <= n; i++){if(d[i] > w){w = d[i]; u = i;}}
//printf("w = %d u = %d\n", w, u);
memset(judge, 0, sizeof(judge));
bfs(u);bo = false;
for(i = 1; i <= n; i++){
if(d[i] >= s){puts("YES");bo = true;break;}
}
if(!bo)puts("NO");
}
}
}
return 0;
}