题解 P2865 【[USACO06NOV]路障Roadblocks】

· · 题解

一句话 深搜（DFS）

由于数据水才容本蒟蒻说此话

既然是求次短路，那么先捣鼓出最短路做标准，再深搜求解；

设最短路长为s1,与结点n相连的最短边的长度为c，设s2=s1+2*c,则s2就是次短路长度的上界。接下来我们只要进行DFS深搜即可，在搜索过程中利用上界s2进行剪枝，并不断更新s2，就可以在题目规定的时间内得到结果。

话不多说，上代码；


#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

int n,m;
int x,y,z,T;
int ans[1000000];
int head[200500],cnt;
int dis[200500];
bool done[200500];
struct node {
    int nxt,to,dis;
}e[200500];

inline void cdp(int from,int to,int dis) {
    cnt ++;
    e[cnt].to = to;
    e[cnt].dis = dis;
    e[cnt].nxt = head[from];
    head[from] = cnt;
}

int numm;
void dfs(int x,int nt) {
    if(x == n) {
        if(nt != dis[n]) T = min(T,nt);
        return ;
    }
    if(nt > T) return ;

    for(int i = head[x]; i ;i = e[i].nxt) {
        if(done[e[i].to]) continue ;
        else {
            done[e[i].to] = true;
            dfs(e[i].to,nt + e[i].dis);
            done[e[i].to] = false;
        }
    }
}

queue< int > q;
inline void spfa() {
    for(int i = 1;i <= n;i ++) dis[i] = 999999999,done[i] = 0;
    dis[1] = 0;
    done[1] = 1;
    q.push(1); 
    while(!q.empty()) {
        int u = q.front();q.pop();
        done[u] = 0;
        for(int i = head[u]; i ;i = e[i].nxt) {
            if(dis[e[i].to] > dis[u] + e[i].dis) {
                dis[e[i].to] = dis[u] + e[i].dis;
                if(!done[e[i].to]) {
                    q.push(e[i].to);
                    done[e[i].to] = 1; 
                }
            }
        }
    }
}

int main() {
    // freopen("maze.in","r",stdin);
    //freopen("maze.out","w",stdout);

    int maxx = 999999999;

    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i ++) {
        scanf("%d%d%d",&x,&y,&z);
        cdp(x,y,z);cdp(y,x,z);
        if(x == n || y == n) {
            maxx = min(z,maxx);
        }
    }

    spfa();
    T = dis[n] + 2 * maxx;

    dfs(1,0);
    printf("%d",T);

    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
/*
4 4
1 2 2
2 4 4
2 3 3
3 4 4
*/