求助站外题（次短路）

萌新求助次短路问题，现在样例是过了的，但是经过查看输出是某些点输出了 0.00，代码求调，问题如下：（悬赏一个关注）

问题描述

蒜头君陷入了坐标系上的一个迷阵，迷阵上有

n

个点，编号从

1

到

n

。蒜头君在编号为

1

的位置，他想到编号为 n 的位置上。蒜头君当然想尽快到达目的地，但是他觉得最短的路径可能有风险，所以他会选择第二短的路径。现在蒜头君知道了

n

个点的坐标，以及哪些点之间是相连的，他想知道第二短的路径长度是多少。

注意，每条路径上不能重复经过同一个点。

输入格式

第一行输入两个整数

n

(

1≤n≤200

) 和

m

，表示一共有

n

个点和

m

条边。

接下来输入 n 行，每行输入两个整数

x_i,y_i

(

-500≤x_i,y_i\leq 500

)，代表第

i

个点的坐标。

接下来输入

m

行，每行输入两个整数

p_j,q_j

(

1≤p_j,q_j≤n

)，表示点

p_j

和点

q_j

之间相连。

输出格式

输出一行，输出包含一个数，表示第二短的路径长度（小数点后面保留两位），如果第一短路径有多条，则答案就是第一最短路径的长度；如果第二最短路径不存在，则输出 -1。

样例输入

CPP

样例输出

CPP

2.41

CPP

#include<vector>
#include<utility>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,pre[205];
double dis[205],mat[205][205],x[205],y[205];
bool vis[205];
inline double dist(int u,int v){
    return sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]));
}
inline void dijkstra(int st,int del){
    for(int i=1;i<=n;i++){
        dis[i]=inf;
        vis[i]=false;
        if(del==0)pre[i]=-1;
    }dis[st]=0;
    for(int i=1;i<=n;i++){
        int u;
        double mind=inf;
        for(int j=1;j<=n;j++){
            if(dis[j]<mind&&!vis[j])mind=dis[j],u=j;
        }if(mind==inf)return;
        vis[u]=true;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&dis[j]>dis[u]+mat[u][j]){
                dis[j]=dis[u]+mat[u][j];
                if(del==0)pre[j]=u;
            }
        }
    }
}
int main(){
    freopen("marsh.in","r",stdin);
    freopen("marsh.out","w",stdout);
    cin>>n>>m;
    memset(mat,0x3f,sizeof mat);
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        mat[u][v]=mat[v][u]=dist(u,v);
    }dijkstra(1,0);
    int now=n;double ans=inf;
    while(pre[now]!=-1){
        mat[pre[now]][now]=mat[now][pre[now]]=inf;
        dijkstra(1,1);
        ans=min(ans,dis[n]);
        mat[pre[now]][now]=mat[now][pre[now]]=dist(pre[now],now);
        now=pre[now];
    }if(ans==inf)cout<<0<<endl;
    cout<<fixed<<setprecision(2)<<ans<<endl;
    return 0;
}

求助站外题（次短路）

讨论操作

回复

相关推荐

求助站外题（次短路）