傳送門
題意： 給一個圖，111號點(diǎn)為中心點(diǎn)，定義dis[i]dis[i]dis[i]表示111號點(diǎn)到iii的距離。現(xiàn)在有三種移動方式
(1)(1)(1)從iii移動到jjj且dis[i]<dis[j]dis[i]<dis[j]dis[i]<dis[j]。
(2)(2)(2)從iii移動到jjj且dis[i]>=dis[j]dis[i]>=dis[j]dis[i]>=dis[j]。
(3)(3)(3)結(jié)束旅程。
其中第二種移動方式最多只能使用一次。問每個點(diǎn)能到達(dá)的離起點(diǎn)最近的點(diǎn)的距離是多少。
思路： 我們維護(hù)一個dpdpdp數(shù)組，dp[i]dp[i]dp[i]表示iii點(diǎn)能到達(dá)的距離起點(diǎn)最近的距離。轉(zhuǎn)移方程也比較好想啦
{dp[i]=min(dp[i],dp[j]),dis[i]<dis[j]dp[i]=min(dp[i],dis[j]),dis[i]>=dis[j]\begin{cases} dp[i]=min(dp[i],dp[j]),dis[i]<dis[j] \\ dp[i]=min(dp[i],dis[j]),dis[i]>=dis[j] \end{cases}{dp[i]=min(dp[i],dp[j]),dis[i]<dis[j]dp[i]=min(dp[i],dis[j]),dis[i]>=dis[j]?
dp[i]dp[i]dp[i]的初始值為dis[i]dis[i]dis[i]，轉(zhuǎn)移的時候只需要按照disdisdis從大到小轉(zhuǎn)移即可。按照深度排個序就好了，不知道為什么我寫了個優(yōu)先隊(duì)列
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,m
;
int dis
[N
],p
[N
];
int f
[N
],g
[N
];
vector
<int>v
[N
];
bool st
[N
];struct cmp
{bool operator () (int a
,int b
){return dis
[a
]<dis
[b
];}
};int main()
{
int _
; scanf("%d",&_
);while(_
--){scanf("%d%d",&n
,&m
);for(int i
=1;i
<=n
;i
++) v
[i
].clear(),st
[i
]=false,p
[i
]=i
,dis
[i
]=INF
;for(int i
=1;i
<=m
;i
++){int a
,b
; scanf("%d%d",&a
,&b
);v
[a
].pb(b
);}dis
[1]=0; st
[1]=true;queue
<int>qq
; qq
.push(1);while(qq
.size()){int t
=qq
.front(); qq
.pop();for(auto x
:v
[t
]) if(!st
[x
]) dis
[x
]=dis
[t
]+1,qq
.push(x
),st
[x
]=true;}priority_queue
<int,vector
<int>,cmp
>q
;int mx
=0;for(int i
=1;i
<=n
;i
++) st
[i
]=false,f
[i
]=dis
[i
];for(int i
=1;i
<=n
;i
++) q
.push(i
),st
[i
]=true;while(q
.size()){int u
=q
.top(); q
.pop();for(auto x
:v
[u
]){if(dis
[x
]>dis
[u
]) f
[u
]=min(f
[u
],f
[x
]);else f
[u
]=min(f
[u
],dis
[x
]);if(!st
[u
]) q
.push(u
),st
[u
]=true;}}for(int i
=1;i
<=n
;i
++) printf("%d ",f
[i
]);}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的Codeforces Round #693 (Div. 3) G. Moving to the Capital dp + 思维的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
