题解 P2910 【[USACO08OPEN]寻宝之路Clear And Present Danger】

zumgze · 2019-08-14 20:58:16 · 题解

这是一道图论题（甚至还是完全图），危险度就相当于边权（甚至输入数据就是邻接矩阵），最小危险度就是最短距离

那么，就来到了最短路算法 n次dj/floyd（这里是dj）

发现其他题解基本都是floyd，剩下用了dj的也没有用优先队列优化dj的 用优先队列优化dj就是用优先队列的pop来代替每次遍历邻接矩阵找最短边，可以把n^2的复杂度优化到n*log（n）

#include<iostream>
#include<queue>
using namespace std;
int a[100][100];
int ans[10000];
struct node//用于dj中的优先队列 
{
    int no,dis;
    node(int a,int b)
    {
        no=a;
        dis=b;
    }
};
bool operator<(node a,node b)
{
    return a.dis>b.dis;
}
bool operator>(node a,node b)
{
    return a.dis<b.dis;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)cin>>ans[i];//储存需要依次经过的点 
    for(int i=0;i<n;i++)//读入，初始化图 
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    for(int i=0;i<n;i++)//每次计算i到其他各个点的最短路 
    {
        priority_queue<node> q;
        bool b[100];//判断一个点是否已经使用过 
        for(int j=0;j<n;j++)//把从i出发的每个点及其距离入队列 
            if(i==j)b[j]=false;
            else
            {
                b[j]=true;
                q.push(node(j,a[i][j]));
            }
        for(int j=0;j<n-1;j++)
        {           
            while(!b[q.top().no])q.pop();
            node now=q.top(); 
            b[now.no]=false;//标记 
            a[i][now.no]=now.dis;//更新图 
            for(int k=0;k<n;k++)//把从i出发途径now（当前位置）的每个点及其距离入队列 
                q.push(node(k,now.dis+a[now.no][k]));
        }
    }//现在a[i][j]就是i到j的最短距离了 
    long long kotae=0;
    for(int i=1;i<m;i++)//依次累加需要经过的点之间的距离 
        kotae+=a[ans[i-1]-1][ans[i]-1];
    cout<<kotae;
    return 0;
}