#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 过了，应该不是数据很水吧，做法如下 (1895) lmc596922196 2015-08-17 09:59:37
  • Re:Spfa + dfs 过了，应该不是数据很水吧，做法如下 (25) lmc596922196 2015-08-17 10:00:15