//342.道路与航线
//分析:最短路问题,且有负权边,因此考虑使用spfa算法
//同时,注意到城镇数以及航线+道路的数量皆为1e5的量级,因此即便是spfa的nlogn也会TLE
//因此,考虑使用双端队列优化
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e6+10;
//道路具有一个性质,那便是双向性
//航路具有两个性质:单向性、两点间无法通过道路回溯
//道路与航路的第一个性质控制邻接表的建立次数即可解决,对于两点间无法通过道路回溯的问题,则需要针对终点添加一个标记
//表明它是航路的末端
int h[N],e[N],ne[N],w[N];//邻接表存储图
int p_h[N];//指示为航路的末端
int idx;//指示当前所处理的下标
int T,R,P,S;
int dist[N];//记录距离
bool st[N];//记录是否走过
bool is_valid(int a,int b)
{
for(int i =p_h[a];i!=-1;i = ne[i])//通过道路来回溯,如果航路的两端可以通过道路来回去,那必然不合法
if(e[i] == b) return false;
return true;
}
void add(int a,int b,int c)
{
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
void add_p(int a,int b)
{
//这里体现了航路与道路共用一个邻接表
e[idx] = b;
//为航路的终点添加标记
ne[idx] = p_h[a];
p_h[a] = idx++;
}
void spfa()
{
deque<int> q;
q.push_back(S);//将S点放入双端队列中
st[S] = true;
dist[S] = 0;//中央城镇到自己的距离必然是0
while(q.size())
{
int t = q.front();
q.pop_front();
st[t] = false;
for(int i =h[t];i!=-1;i = ne[i])
{
int j = e[i];
if(is_valid(t,j)&&dist[j]>dist[t]+w[i])//如果两点之间不存在直达航路
{
dist[j] = dist[t]+w[i];
if(!st[j])
{
st[j] = true;
if(q.size()&&dist[j]<dist[q.front()])q.push_front(j);//双端队列优化
else q.push_back(j);
}
}
}
}
}
int main()
{
cin>>T>>R>>P>>S;
//初始化
memset(st,false,sizeof st);
memset(dist,0x3f,sizeof dist);
memset(h,-1,sizeof h);
memset(p_h,-1,sizeof p_h);
for(int i = 1;i<=R;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
for(int i =1;i<=P;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);//与道路存储与同一个邻接表内
add_p(b,a);//为航路末端添加标记
}
spfa();
for(int i =1;i<=T;i++)
{
if(dist[i]>(0x3f3f3f3f)/2)puts("NO PATH");
else cout<<dist[i]<<endl;
}
}
spfa还可以用双端队列优化吗,楼主可以问一下这个知识点的话y总有在课里讲过么