> #include<iostream>
> #include<cstdio>
> #include<cmath>
> #include<cstring>
> using namespace std;
> const int INF = 0x3f3f3f3f;
> const int maxn = 5005;
> const int maxm = 100005;
> struct EDGE{
>     int v, w, next;
> }E[maxm << 1];
> int head[maxn], tol, n, m;
> int dis[maxn], vis[maxn];
> int Q[maxn << 1], front, rear;
> 
> void Init(){
>     memset(head, -1, sizeof head);
>     tol = 0;
> }
> 
> void add_edge(int u, int v, int w){
>     E[tol].v = v;
>     E[tol].w = w;
>     E[tol].next = head[u];
>     head[u] = tol++;
> }
> 
> void Spfa(){
>     for(int i = 0; i <= n; i++){
>         dis[i] = INF;
>         vis[i] = 0;
>     }
>     dis[n] = 0;
>     vis[n] = 1;
>     front =  rear = 0;
>     Q[ rear++ ] = n;
>     while(front < rear){
>         int u = Q[ front++ ];
>         for(int i = head[u]; i != -1; i = E[i].next){
>             int v =  E[i].v;
>             if(dis[v] > dis[u] + E[i].w){
>                 dis[v] = dis[u] + E[i].w;
>                 if(!vis[v]){
>                     vis[v] = 1;
>                     Q[ rear++ ] = v;
>                 }
>             }
>         }
>     }
> }
> 
> int ans, sr;
> void dfs(int u, int res){
>     if(res + dis[u] >= ans) return;
>     if(res + dis[u] > sr){
>         ans = res + dis[u];
>     }
>     for(int i = head[u]; i != -1; i = E[i].next){
>         int v = E[i].v;
>         dfs(v, res + E[i].w);
>     }
> }
> 
> int main(){
>     int u, v, w;
>     while(scanf("%d%d", &n, &m) != EOF){
>         Init();
>         for(int i = 1; i <= m; i++){
>             scanf("%d%d%d", &u, &v, &w);
>             add_edge(u, v, w);
>             add_edge(v, u, w);
>         }
>         Spfa();
>         sr = dis[1];
>         ans = INF;
>         dfs(1, 0);
>         printf("%d\n", ans);
>     }
>     return 0;
> }
> 
> 
> 
> 

• Re:Spfa + dfs 过了，应该不是数据很水吧，做法如下 (25) lmc596922196 2015-08-17 10:00:15