题意是给一幅图可以把 k 条边权值变为 0, 求最短路.
分层图裸题, 分层图忘完了啊, 还在预流推进那做过几道题, 难受.
分层图就是再开一维数组记录额外的状态, 这道题可以把 k 条边权值变为 0, 那那一维数组 j 就表示有 j 条边权值为 0, 做个 dp 就好.
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int M = 1e5+7;
- const ll inf = 1e18;
- int _,n,m,k;
- int cnt,head[M],flag[M][13];
- struct edge
- {
- int v,next;ll w;
- }e[M<<1];
- void init(){
- cnt=0;memset(head,-1,sizeof(head));memset(flag,0,sizeof(flag));
- }
- void add(int u,int v,ll w){
- e[++cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];
- head[u]=cnt;
- }
- struct node
- {
- int index,level;ll dis;
- bool operator <(const node & k) const{
- return dis>k.dis;
- }
- }d[M][13];
- void dijkstra(int s){
- for(int i=1;i<=n;i++)
- for(int j=0;j<=k;j++) d[i][j].dis=inf,d[i][j].index=i,d[i][j].level=j;
- priority_queue<node> q;d[s][0].dis=0;q.push(d[s][0]);
- while(!q.empty()){
- int u=q.top().index,lv=q.top().level;q.pop();
- if(flag[u][lv]) continue;
- flag[u][lv]=1;
- for(int i=head[u];~i;i=e[i].next){
- int v=e[i].v;ll w=e[i].w;
- if(d[v][lv].dis>d[u][lv].dis+w){// 同一层的最短路径
- d[v][lv].dis=d[u][lv].dis+w;
- q.push(d[v][lv]);
- }
- if(lv<k&&d[v][lv+1].dis>d[u][lv].dis){// 如果这条边不选那么就会多一条边不选, 状态转移到了 lv+1 这一层
- d[v][lv+1].dis=d[u][lv].dis;
- q.push(d[v][lv+1]);
- }
- }
- }
- ll ans=d[n][0].dis;
- for(int i=1;i<=k;i++){
- ans=min(ans,d[n][i].dis);
- }
- printf("%lld\n",ans);
- }
- int main(){
- scanf("%d",&_);
- while(_--){
- init();
- scanf("%d%d%d",&n,&m,&k);
- for(int i=1;i<=m;i++){
- int u,v;ll w;
- scanf("%d%d%lld",&u,&v,&w);
- add(u,v,w);
- }
- dijkstra(1);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2751840.html