-> https://www.luogu.org/problemnew/show/P1186
题意: 有 n 个点, m 条无向边, 问从 1 到 n(或从 n 到 1) 的一个最长时间 t, 且满足删除任意一条边后, 得到的最短路都小于等于这个时间 t.
思路: 可以发现只有删除最短路上的边时才会对答案有影响. 因此我们枚举最短路上的每一条边, 将它们删去后跑最短路, 最后取 max 即为答案. 注意删边后图要保证连通.
代码:
60pt: 枚举每条边
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<queue>
- using namespace std;
- const int N=1000+100,M=500000+10;
- int n,m;
- struct node{
- int to,nxt,w;
- }e[M<<1];
- int head[N],tot=1;
- void add(int u,int v,int w){
- e[++tot]=(node){v,head[u],w};
- head[u]=tot;
- }
- queue<int>q;
- bool vis[N];
- int dis[N];
- int SPFA(int edge){
- while(q.size()) q.pop();
- for(int i=1;i<=n;i++) {
- vis[i]=false;
- dis[i]=(1<<30);
- }
- dis[1]=0,vis[1]=true;
- q.push(1);
- while(q.size()){
- int u=q.front();q.pop();vis[u]=0;
- 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;
- if(!vis[v]){
- q.push(v);vis[v]=1;
- }
- }
- }
- }
- return dis[n];
- }
- int main() {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;i++){
- int u,v,w;
- scanf("%d%d%d",&u,&v,&w);
- add(u,v,w);
- add(v,u,w);
- }
- int ans=SPFA(tot+233);
- for(int i=1;i<=tot;i++){
- int x=e[i].w;
- e[i].w=(1<<30);
- int now=SPFA(i);
- e[i].w=x;
- if(now!=(1<<30)) ans=max(ans,now);
- }
- printf("%d",ans);
- return 0;
- }
100pt: 枚举最短路
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<queue>
- using namespace std;
- const int N=1000+100,M=500000+10;
- int n,m;
- struct node{
- int fro,to,nxt,w;
- }e[M<<1];
- int head[N],tot=1;
- void add(int u,int v,int w){
- e[++tot]=(node){u,v,head[u],w};
- head[u]=tot;
- }
- queue<int>q;
- bool vis[N];
- int dis[N];
- int pre[N];
- // 通过记录每个点的前驱来记录最短路路径
- bool f;
- // 标记是否为第一次 SPFA, 即是否要记录前驱
- void SPFA(){
- while(q.size()) q.pop();
- for(int i=1;i<=n;i++) {
- vis[i]=false;
- dis[i]=(1<<30);
- // 千万别像我把 pre 初始化了
- }
- dis[n]=0,vis[n]=true;
- q.push(n);
- while(q.size()){
- int u=q.front();q.pop();vis[u]=0;
- for(int i=head[u];i;i=e[i].nxt){
- int v=e[i].to;
- if(dis[v]>dis[u]+e[i].w){
- if(!f)
- // 因为要求最初的最短路路径
- // 所以只有第一次最短路时才记录每个点的前驱
- pre[v]=i;
- dis[v]=dis[u]+e[i].w;
- if(!vis[v]){
- q.push(v);vis[v]=1;
- }
- }
- }
- }
- }
- int main() {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;i++){
- int u,v,w;
- scanf("%d%d%d",&u,&v,&w);
- add(u,v,w);
- add(v,u,w);
- }
- SPFA();
- f=true;
- int ans=dis[1];
- for(int i=pre[1];i;i=pre[e[i].fro]){
- // 枚举记录的最短路路径
- int x=e[i].w;
- e[i].w=(1<<30);
- SPFA();
- e[i].w=x;// 回溯
- if(dis[1]!=(1<<30)) // 图要保证连通
- ans=max(ans,dis[1]);
- }
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2592603.html