codeforces round 974(div.3)E(优先队列实现dijstra算法，devc++的优先队列用greater报错)
解题历程：
看到两边同时移动，计算最终的相遇时间，我就想到两边同时计算各点到起点的最短距离，就是使用dijstra算法，最后所有节点取两次计算的最大值，再对所有节点取最小值，就是最终答案了，可是这个思路没有考虑有马的情况，思考一番后发现可以多列一个数组记录有马的情况下的行走最短路，然后将有马和无马取最小值合并成单源最短路的结果
代码：
#include<bits/stdc++.h>
#define ll long long
#define inf 1e18
using namespace std;
void solve() {
int n,m,h;
cin>>n>>m>>h;
vector<vector<pair<ll,ll>>>a(n+1);
vector<int>horse(n+1,0);
for(int i=0;i<h;i++)
{
int l;
cin>>l;
horse[l]=1;
}
for(int i=1;i<=m;i++)
{
ll u,v,w;
cin>>u>>v>>w;
a[u].push_back({v,w});
a[v].push_back({u,w});
}
auto dijstra=[&](int s){
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<>>pq;//devc++要用greater<ll>
vector<ll>vis(2*n+5,inf);
pq.push({0ll,2*s});
while(!pq.empty()){
ll d=pq.top().first;
ll u=pq.top().second;
pq.pop();
if(vis[u]!=inf)continue;
vis[u]=d;
int x=u%2;
int y=(u+1)/2;
if(x==0&&horse[y])
{
pq.push({d,y*2-1});
}
for(auto t:a[y])
{
pq.push({d+t.second/(1+x),2*t.first-x});
}
}
vector<ll>d(n+1,inf);
for(int i=1;i<n+1;i++)
{
d[i]=min(vis[i*2],vis[2*i-1]);
}
return d;
};
auto dl=dijstra(1);
auto dr=dijstra(n);
ll ans=inf;
for(int i=0;i<n;i++)
{
ans=min(ans,max(dl[i+1],dr[i+1]));
}
if(ans!=inf)
cout<<ans<<endl;
else
cout<<-1<<endl;
}
int main(void )
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int test=1;
cin>>test;
while(test--)
{
solve();
}
return 0;
}
感悟：
-
以后卡题了可以考虑多开数组记录数据，算法竞赛不用省空间
-
优先队列的dijstra算法要实现的话只需要一个优先队列，一个数组，优先队列用pair容器，pair用于存储该点的编号和该点到起点的距离，数组起始都是inf，用于记录对应编号的点到起点的最短距离。首先将起点和距离0装入队列。然后循环以下操作：将队首出队，队首是队列中离起点最近的点，判断该点是否已经赋值过，若是没有被赋值过，则将该距离赋给该点，否则就不赋值跳过后面的操作，赋值后将该点相关联的点和父点的离起点的距离加上父点到该点的距离一起存入队列。循环以队列为空时停止，此时数组的数值就是对应点到起点的最短路径了。
-
dijstra算法的思想和dp非常的像，都是将局部的最优解存起来，在后面的步骤可以直接用，这样可以省去重复的计算
-
devc++有一个坑点，优先队列中的greater<>中尖括号内需要加上变量类型，比如greater< int >，不然的话会报错，有些编译器不加也能运行