题意

题目给你的意思就是

求1到n的

必须经过一些点（2→k+1）

而且过这些点还要讲先后顺序

的最短路长度

解题

首先看到k<=20

它这是告诉你

对于这k个必须经过的点

你怎么暴力怎么搞

所以我们对这k个点每个点单元最短路（dijkstra）一下，求出他们到所有点的距离。dis[i][j]表示由i出发到j的距离

然后是处理先后关系。我们建立一个数组r[i]，r[i]的值，表示到达第i个点之前，必须停留的点的状压集合，1为必经，0为无所谓（因为k<=20所以可以状压）

接着就是状压DP。这里f[i][j]表示当前状态集合为i（1为停留过，0为没有），目前停留在j的最短路径。

转移就是普通状压dp套路，从0到（1<<k-1）[全都有] 枚举状态，找到一个集合中存在的点和一个集合中不存在的点，如果当前状态满足这个不在集合内的点的r[i]（也就是经过它之前必须经过的点都经过了）那么就进行转移。

初始状态，f设为INF,如果一个点i在停留之前不需要在任何点停留，那么f[1][i]=dis[1][i]，f[0][1]=0

几点注意（长者的经验教训）

1.当k=0时直接跑最短路不然会WA第六个点

2.INF不能开太大（第三个点会爆成负数）

3.数组要卡空间，不然要么RE要么MLE

4.如果数组太大最好不用memset，最好自己给数组赋值，这样会快很多

5.注意位运算的先后顺序，能打括号就打括号。

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define rg register int#define RG register#define ll long long#define il inline#define INF 1000000000 // INF 不要太大会飞起#define mk make_pairusing namespace std;typedef pair 
         
           P;il int gi(){ rg x=0,o=0;RG char ch=getchar(); while((ch!='-')&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') o=1,ch=getchar(); while('0'<=ch&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return o?-x:x;}struct Edge{int to,nxt,w;}e[300001];int Ehead[30001],Ecnt=1;il void Eadd(rg u,rg v,rg w){ e[Ecnt]=(Edge){v,Ehead[u],w}; Ehead[u]=Ecnt++; e[Ecnt]=(Edge){u,Ehead[v],w}; Ehead[v]=Ecnt++;}int n,m,k,g;int r[32],dis[32][30001];priority_queue 
          
           ,greater
            > Q;il void dijkstra(rg rt){ for(rg i=1;i<=n;++i) dis[rt][i]=INF; while(!Q.empty()) Q.pop(); Q.push(mk(0,rt));dis[rt][rt]=0; while(!Q.empty()) { rg u=Q.top().second;Q.pop(); for(rg i=Ehead[u];i;i=e[i].nxt) { rg v=e[i].to; if(dis[rt][v]>dis[rt][u]+e[i].w) { dis[rt][v]=dis[rt][u]+e[i].w; Q.push(mk(dis[rt][v],v)); } } }}// dijkstra 无vis数组int f[1<<20][25],Ans=INF;int a,b,u,v,w;int main(){ n=gi(),m=gi(),k=gi(); for(rg i=1;i<=m;++i) { u=gi(),v=gi(),w=gi(); Eadd(u,v,w); } if(!k) { dijkstra(1); printf("%d",dis[1][n]); return 0; } //不加这个判断第6个点会WA g=gi(); for(rg i=1;i<=g;++i) { a=gi(),b=gi(); r[b] |= (1<<(a-2)); } for(rg i=1;i<=k+1;++i) dijkstra(i); for(rg i=0;i<=(1<

转载于:https://www.cnblogs.com/tply/p/8274275.html

你可能感兴趣的文章