题解 P2966 【[USACO09DEC]牛收费路径Cow Toll Paths】

· · 题解

居然发现没有人写dijkstra的算法过这个题

那我这个水过的蒟蒻就来讲讲dijkstra怎么做

如果不会dijkstra 请先进这个题进行学习qwq

这个思路比较清奇

首先 我们这个题目中有个坑点 就是说 每一次要加上走过路径之中点权最大的点

其实很好想的就是每一次处理的时候存一下最大点权 然后就发现 不是TLE即MLE

然后 我们就有了这个思路：

1 一重循环k 表示当前我们这条路上的最大点权 即所有可经过点的点权≤点k的权值

2 在循环k里面做dijkstra 注意经过的点只能是点权≤k点的 不然就错了

3 在更新完dist后 计算答案 计算式要加上k点的点权

这样一分析 时间复杂度Θ（n^3) 美妙卡过

最后来上一发代码（要抄也得先理解思路）

//这里写一笔 我的标程没有写链式前向星 用的是邻接矩阵
#include<bits/stdc++.h>
using namespace std;
// n,m,query 就是n,m,k
// p代表点的权值 maze是邻接矩阵 dist是处理出来的某个点到所有点的最小值(dijkstra) vis标记 ans不必多说 储存答案 
int n,m,query;
int p[260],maze[260][260],dist[260],ans[260][260],vis[260]; 
void dijkstra(int k){
//当然 数组不清空 交题见祖宗 
    memset(vis,0,sizeof(vis));
    memset(dist,0x3f,sizeof(dist));
    //以下是disjktra正常操作 
    dist[k]=0; 
    for(int i=1;i<=n;i++){
        int v=-1;
        /*看到这里你可能会奇怪 (p[u]<=p[k]) 什么鬼
    其实很好理解的 我把我每一次做dijkstra的点拉出来 做为当前的最大点权 那当然不可以进入比最大点权权值还要大的点了 */ 
        for(int u=1;u<=n;u++) if(((dist[u]<dist[v])||(v==-1))&&(p[u]<=p[k])&&(!vis[u])) v=u;
        if(v==-1) break;
        vis[v]=true;
        //其实这里(p[u]>p[k])跟上面那个一样的 然后就dijkstra正常走一波 
        for(int u=1;u<=n;u++){
            if(p[u]>p[k]) continue;
            dist[u]=min(dist[u],dist[v]+maze[v][u]);
        }
    }
}
int main(){
    //清空赋值读入 这里就不多讲了
    memset(ans,0x3f,sizeof(ans));
    memset(maze,0x3f,sizeof(maze));
    cin>>n>>m>>query;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        maze[a][b]=maze[b][a]=min(maze[a][b],c);
    }
    //这里的k代表的是当前我选中的点 这个点代表了当前的最大点权 即在本次我dijkstra中选出可用的点的点权不可以有大于它的 
    for(int k=1;k<=n;k++){
        dijkstra(k);//进函数
        //下面是计算ans 这里计算ans是由选出的最大点权的点到任意两个点的距离 别忘了加上最大点权 
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                ans[i][j]=min(ans[i][j],dist[i]+dist[j]+p[k]);
    }
    //对于每一次询问 我们处理出它的答案:) 
    for(int i=1;i<=query;i++){
        int a,b;
        cin>>a>>b;
        cout<<ans[a][b]<<endl;
    }
    return 0;
}