分层图最短路处女作TAT

很明显要求你求一个分层图上的最短路。不过没必要把分层图构出来，手写转移即可。还有卡SPFA是怎么回事？出题人你粗来我保证不打死你……

然而沉迷pb_ds，不能自拔。

代码：

/**************************************************************
    Problem: 2763
    User: danihao123
    Language: C++
    Result: Accepted
    Time:268 ms
    Memory:3136 kb
****************************************************************/
 
#include <cstdio>
#include <queue>
#include <algorithm>
#include <utility>
#include <cstring>
#include <cctype>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
const int maxn=10001,maxm=100001,maxk=11;
typedef pair<int,int> pii;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
inline void Add_Edge(int u,int v,int d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
struct Node{
    pii pnt;
    int d;
    bool operator <(const Node& x) const{
        return d<x.d;
    }
    bool operator >(const Node& x) const{
        return d>x.d;
    }
};
 
typedef __gnu_pbds::priority_queue<Node,greater<Node> > Heap;
Heap::point_iterator ite[maxn][maxk];
Heap Q;
int n,k;
bool vis[maxn][maxk];
int d[maxn][maxk];
inline void relax(int u,int v,int di){
    d[u][v]=di;
    if(ite[u][v]!=0)
        Q.modify(ite[u][v],(Node){make_pair(u,v),di});
    else
        ite[u][v]=Q.push((Node){make_pair(u,v),di});
}
int Dijkstra(int s,int t){
    register int i,u,v;
    pii temp;
    memset(d,0x7f,sizeof(d));
    d[s][0]=0;
    ite[s][0]=Q.push((Node){make_pair(s,0),0});
    while(!Q.empty()){
        temp=Q.top().pnt;
        Q.pop();
        u=temp.first;
        v=temp.second;
        if(vis[u][v])
            continue;
        vis[u][v]=true;
        for(i=first[u];i;i=next[i]){
            if(v<k){
                if(d[u][v]<d[to[i]][v+1]){
                    relax(to[i],v+1,d[u][v]);
                }
            }
            if(d[u][v]+dist[i]<d[to[i]][v]){
                relax(to[i],v,d[u][v]+dist[i]);
            }
        }
    }
    register int ans=0x7f7f7f7f;
    for(i=0;i<=k;i++)
        ans=min(ans,d[t][i]);
    return ans;
}
int main(){
    int m,s,t,u,v,d;
    register int i;
    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&d);
        Add_Edge(u,v,d);
        Add_Edge(v,u,d);
    }
    printf("%d\n",Dijkstra(s,t));
    return 0;
}

• 相关文章
• 全局相关文章