P5304

啊,这题其实比较简单。

然后对于这个程序


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
inline long long read(){long long x;scanf("%lld",&x);return x;}
const long long N=15+5,M=75+5,inf=1e15;
long long T,n,m,k,in[N],ans;

long long fir[N],pre[M],nex[M],to[M],val[M],pos=0;
void add(long long x,long long y,long long v){
    to[++pos]=y;pre[pos]=x;nex[pos]=fir[x];fir[x]=pos;val[pos]=v;
}
void _delete(long long x){
    long long u=pre[x];
    fir[u]=nex[fir[u]];
    pre[x]=nex[x]=to[x]=val[x]=0;
}

void clear(){
    memset(in,0,sizeof(in));
    memset(fir,0,sizeof(fir));
    memset(nex,0,sizeof(nex));
    memset(to,0,sizeof(to));
    memset(val,0,sizeof(val));
    pos=0;ans=inf;n=m=k=0;
}

struct node{long long dian,far;}c;
bool operator <(node a,node b){return a.far>b.far;}
priority_queue<node> q;
long long dis[N],s,t;
long long dijk(){
    for(int i=s;i<=t;++i) dis[i]=inf;
    long long u=s;dis[s]=0;
    c.dian=s;c.far=0;q.push(c);
    while(!q.empty()){
        c=q.top();q.pop();u=c.dian;
        if(u==t) break;
        if(c.far>dis[c.dian])continue;
        for(long long i=fir[u];i;i=nex[i]){
            long long v=to[i];
            if(dis[u]+val[i]>=dis[v]) continue;
            dis[v]=dis[u]+val[i];
            c.dian=to[i];c.far=dis[v];
            q.push(c);
        }
    }
    while(!q.empty()) q.pop();
    return dis[t];
}

int main(){
    freopen("in.txt","r",stdin);
    T=read();
    while(T--){
        clear();
        n=read(),m=read(),k=read();
        for(long long i=1;i<=m;++i){
            long long x=read(),y=read(),z=read();
            if(x!=y) add(x,y,z);
        }
        for(long long i=1;i<=k;++i)
          in[read()]=1;
        s=0,t=n+1;
        for(long long l=1;l<=n;l<<=1){
            for(long long u=1;u<=n;++u)
              if(in[u])
                u&l?add(s,u,0):add(u,t,0);
            ans=min(ans,dijk());
            for(long long i=m+1;i<=pos;++i)
              _delete(i);
            pos=m;
        }
        for(long long l=1;l<=n;l<<=1){
            for(long long u=1;u<=n;++u)
              if(in[u])
                u&l?add(u,t,0):add(s,u,0);
            ans=min(ans,dijk());
            for(long long i=m+1;i<=pos;++i)
              _delete(i);
            pos=m;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

它是错的

跑得时候会跑出dis[t]=0来

原因是实际的边数没有m条,在pos-m编号的临时边没有被删去

发表评论

邮箱地址不会被公开。 必填项已用*标注