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;
}