看看代码就懂分层最短路什么意思了

qq姐给我讲的w

不记得是gg多久前布置的题了

反正

很久不打代码

手指似乎都不会用了

好僵硬啊。。。

#include
      
       #include
       
        #define sev enusing namespace std;#define INF 2147483647#define N 10000010priority_queue
        
         
          ,vector
          
           
             >,greater
            
             
               > >q;struct EDGE{ int nxt,to,w;}e[N];int head[N],vis[N],dis[N],cnt;void add(int x,int y,int z) { e[++cnt].to = y; e[cnt].w = z; e[cnt].nxt = head[x]; head[x] = cnt;}int main() { int n,m,k; scanf("%d%d%d",&n,&m,&k); int s,t; scanf("%d%d",&s,&t); for(int i = 1; i <= m; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); for(int j = 1; j <= k; j++) { add(a + j * n,b + j * n,c); add(b + j * n,a + j * n,c); add(a + (j - 1) * n,b + j * n,0); add(b + (j - 1) * n,a + j * n,0); } } for(int i = 0; i <= n; i++) for(int j = 0; j <= k; j++) dis[i + j * n] = INF; dis[s] = 0; q.push(make_pair(0,s)); while(!q.empty()) { int u = q.top().second; q.pop(); if(vis[u]) continue; vis[u] = 1; for(int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if(dis[v] > dis[u] + e[i].w) { dis[v] = dis[u] + e[i].w; q.push(make_pair(dis[v],v)); } } } int ans = INF; for(int i = 0; i <= k; i++) ans = min(ans,dis[t + i * n]); printf("%d",ans); return 0;}
             
            
           
          
         
        
       
      

不知道该感慨些什么

总是听歌听得很丧

总是对自己很失望

总是觉得无可爱

哎

为什么总有告诉他我喜欢他的冲动呢