P1186题解

· · 题解

题解

笔者一看这道题，盲目认为题目超水，果断写了一个 dijkstra,然后枚举每一条最短路的边，将其删去，然后再跑一遍 dijkstra 求当前最短路，如果当前的最短路大于 ans 就更新，这样就求出了最大次短路。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define reg register
#define ri reg int

struct node{
    ll v,w,nxt;
}edge[2001000];

ll n,m,u,v,w;

ll head[1100],dis[1100],pre[1100],pred[1100];

bool vis[1100];

ll tot;

inline void Add_edge(ll u,ll v,ll w){
    edge[++tot].v=v;
    edge[tot].nxt=head[u];
    edge[tot].w=w;
    head[u]=tot;
}

priority_queue<pair<ll ,ll > > Q;

void Dij(){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    Q.push(make_pair(0ll,1ll));
    dis[1]=0;
    while(Q.size()){
        ll x=Q.top().second;
        Q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(ll i=head[x];i;i=edge[i].nxt){
            ll v=edge[i].v;
            if(dis[v]>dis[x]+edge[i].w){
                pre[v]=x;
                if(i%2)pred[v]=i;
                else pred[v]=i-1;
                dis[v]=dis[x]+edge[i].w;
                Q.push(make_pair(-dis[v],v));
            }
        }
    }
}

void _Dij(){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    Q.push(make_pair(0ll,1ll));
    dis[1]=0;
    while(Q.size()){
        ll x=Q.top().second;
        Q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(ll i=head[x];i;i=edge[i].nxt){
            ll v=edge[i].v;
            if(dis[v]>dis[x]+edge[i].w){
                dis[v]=dis[x]+edge[i].w;
                Q.push(make_pair(-dis[v],v));
            }
        }
    }
}

int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=m;i++){
        scanf("%lld%lld%lld",&u,&v,&w);
        Add_edge(u,v,w);
        Add_edge(v,u,w);
    }
    Dij();
    ll ans=-1;
    for(ll i=n;i;i=pre[i]){
        ll p=edge[pred[i]].w;
        edge[pred[i]].w=1e17;
        edge[pred[i]+1].w=1e17;
        _Dij();
        edge[pred[i]].w=p;
        edge[pred[i]+1].w=p;
        ans=max(dis[n],ans);
    }
    printf("%lld",ans);
    return 0;
}

但不知道那个毒瘤大佬出的最后三个数据，无论怎么优化，都丝毫无法撼动那三个 TLE，但我丝毫不动摇决心，决定要搞事。

看到我的代码是遍历最短路的每一条边，于是身为喜欢玄学的蒟蒻，于是我加了一个非常看脸的东东，其名曰：

clock()

我们用 clock()，等到快到超时的时候就跳出，直接输出 ans,加上后，一交：

Wrong Answer

让我们先想想为啥会 WA。

我们是从后往前遍历，但可能是要删前面的边才会出答案，那么我们用一个数组正序存起来，然后在遍历试试。

  int ans=-1,flag=0,now=n,nu;
  while(now!=1){
    way[++nu]=pred[now];
    now=pre[now];
  }

然后，我又将 long long 全部改 int,加上快读快写，然后

附上 AC 代码：

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define ri reg int

struct node{
    int v,w,nxt;
}edge[2001000];

int n,m,u,v,w;

int head[1100],dis[1100],pre[11000000],pred[11000000],way[110000000];

bool vis[1100];

int tot;

void z(int &x){ 
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}

inline void Add_edge(int u,int v,int w){
    edge[++tot].v=v;
    edge[tot].nxt=head[u];
    edge[tot].w=w;
    head[u]=tot;
}

priority_queue<pair<int ,int > > Q;

void Dij(){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    Q.push(make_pair(0,1));
    dis[1]=0;
    while(Q.size()){
        int x=Q.top().second;
        Q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(int i=head[x];i;i=edge[i].nxt){
            int v=edge[i].v;
            if(dis[v]>dis[x]+edge[i].w){
                pre[v]=x;
                if(i%2)pred[v]=i;
                else pred[v]=i-1;
                dis[v]=dis[x]+edge[i].w;
                Q.push(make_pair(-dis[v],v));
            }
        }
    }
}

int main(){
    z(n),z(m);
    for(int i=1;i<=m;i++){
        z(u),z(v),z(w);
        Add_edge(u,v,w);
        Add_edge(v,u,w);
    }
    Dij();
    int ans=-1,flag=0,now=n,nu;
    while(now!=1){
        way[++nu]=pred[now];
        now=pre[now];
    }
    for(int i=nu;i>=1;i--){
        int p=edge[way[i]].w;
        edge[way[i]].w=1e9;
        edge[way[i]+1].w=1e9;
        Dij();
        edge[way[i]].w=p;
        edge[way[i]+1].w=p;
        ans=max(dis[n],ans);
        if((double)clock()/CLOCKS_PER_SEC>0.987) break;
    }
    printf("%lld\n",ans);
    return 0;
}

玄学大发好