LibreOJ10072. 「CEOI1999」Sightseeing Trip【最短路】

Sightseeing Trip

【题目描述】

传送门

【题解】

智障的我尽然没有想到Floyed,所以写两个SPFA,枚举边强制不走,然后刷SPFA,x到y的最短路长度。

【代码如下】

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=105;
int n,m,Ans=0,MIN=1e9,hd,tl,Fa[MAXN],cst[MAXN][MAXN],que[MAXN*MAXN*3],dst[MAXN];
bool vis[MAXN];
struct Edge{
    int tot,lnk[MAXN],nxt[MAXN*MAXN],son[MAXN*MAXN],W[MAXN*MAXN];
    void Add(int x,int y,int w){nxt[++tot]=lnk[x];son[tot]=y;W[tot]=w;lnk[x]=tot;}
}E;
struct xcw{int x,y,w;}a[MAXN*MAXN];
void SPFA(int x){
    memset(dst,63,sizeof(dst));
    memset(Fa,0,sizeof(Fa));dst[x]=0;
    hd=0,vis[que[tl=1]=x]=1;
    while(hd^tl){
        x=que[++hd],vis[x]=0;
        for(int j=E.lnk[x];j;j=E.nxt[j])
        if(!cst[x][E.son[j]]&&dst[E.son[j]]>dst[x]+E.W[j]){
            dst[E.son[j]]=dst[x]+E.W[j];Fa[E.son[j]]=x;
            if(!vis[E.son[j]]) que[++tl]=E.son[j],vis[E.son[j]]=1;
        }
    }
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,w;i<=m;i++) scanf("%d%d%d",&x,&y,&w),E.Add(x,y,w),E.Add(y,x,w),a[i]=(xcw){x,y,w};
    for(int i=1;i<=m;i++){
        cst[a[i].x][a[i].y]=1,SPFA(a[i].x),cst[a[i].x][a[i].y]=0;int Now=a[i].w+dst[a[i].y];
        if(MIN>Now) MIN=Now,Ans=i;
    }
    if(!Ans) printf("No solution.\n");
    cst[a[Ans].x][a[Ans].y]=1,SPFA(a[Ans].x);
    int Now=a[Ans].y;
    while(Now){
        printf("%d ",Now);
        Now=Fa[Now];
    }
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部