80pts WA on#1#10,求条并悬2关
查看原帖
80pts WA on#1#10,求条并悬2关
774876
HashHacker_Peas楼主2024/10/4 22:56

rt,思路也是建虚拟源点&汇点,并按位拆点,不明白为什么会WA,求大佬帮忙指出错误 code如下

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define to first
#define dis second
const int maxn=1e5+10;
int t,n,m,u,v,w,k,p[maxn],dis[maxn];
vector<pii>g[maxn];
bool vis[maxn];
struct node{
    int dis,id;
    bool operator<(const node &a)const{
        return a.dis<dis;
    }
};
void dijkstra(int s){
    priority_queue<node>q;
    memset(dis,0x7f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[s]=0;
    q.push((node){0,s});
    while(!q.empty()){
        int x=q.top().id;
        q.pop();
        if(vis[x])
            continue;
        vis[x]=true;
        for(int i=0;i<g[x].size();i++){
            int to=g[x][i].to,dist=g[x][i].dis;
            if(dis[to]>dis[x]+dist){
                dis[to]=dis[x]+dist;
                if(!vis[to])
                    q.push((node){dis[to],to});
            }
        }
    }
}
void init(int n){
    for(int i=0;i<=n+1;i++)
        g[i].clear();
}
signed main(){
    //freopen("P5304.in","r",stdin);
    scanf("%lld",&t);
    while(t--){
        int ans=LONG_LONG_MAX;
        scanf("%lld%lld%lld",&n,&m,&k);init(n);
        while(m--){
            scanf("%lld%lld%lld",&u,&v,&w);
            if(u!=v)g[u].push_back(make_pair(v,w));
            //g[v].push_back(make_pair(u,w));
        }
        for(int i=1;i<=k;i++)
            scanf("%lld",&p[i]);
        for(int i=0;(1<<i)<=k;i++){
            g[0].clear();
            g[n+1].clear();
            vector<int>a,b;
            for(int j=1;j<=k;j++)
                if((p[j]>>i)&1)
                    a.push_back(p[j]);
                else b.push_back(p[j]);
            for(int j=0;j<a.size();j++)
                g[0].push_back(make_pair(a[j],0)),g[a[j]].push_back(make_pair(0,0));
            for(int j=0;j<b.size();j++)
                g[b[j]].push_back(make_pair(n+1,0)),g[n+1].push_back(make_pair(b[j],0));
            dijkstra(0);
            ans=min(ans,dis[n+1]);
            dijkstra(n+1);
            ans=min(ans,dis[0]);
            for(int j=0;j<a.size();j++)
                g[a[j]].pop_back();
            for(int j=0;j<b.size();j++)
                g[b[j]].pop_back();
        }
        printf("%lld\n",ans);
    }
    return 0;
}

2024/10/4 22:56
加载中...