P1673题解
题目意思：
设图
思路
读完题后我们首先应反应到这是求单源最短路，而求单源最短路最快的方法就是 dijkstra，而 dijkstra 最大的弊端是不能处理负权边，但恰好这道题避免了这个 bug （ 每一条边的权值都是
下面用 2 种方法写了一下最短路：
1. dijkstra
算法流程：
假设现在要求出某一点
记
-
从所有从未访问过的点中，找到当前距离最小的，设为
u ，并将其标记为已访问过。 -
调整
u 的所有边（若是有向图则为出边）连接的并且未被访问过的点 ：若weight_{u\to v}+dist_{u}<dist_{v} ，则将dist_{v} 更新为dist_{u}+ weight_{u\to v} 。 -
重复步骤 1 和步骤 2，直到所有点都被标记为已访问过，则
dist_{i} 即s 到i 的最短距离。如果只想求从s 到某一点的最短距离，那么该点被标记为访问过之后可直接退出。
时间复杂度
ACcode
#include<bits/stdc++.h> //万能头
#define maxn 10000005 //太懒别管
#define INF 1e9 //极大值
using namespace std;
struct Edge{
int u,v,w,next;
}edge[maxn];
int head[maxn],cnt,n,m,s,vis[maxn],dis[maxn];
struct node{
int w,now;
inline bool operator <(const node &x)const //根优化
//重载运算符把最小的元素放在堆顶（大根堆）
{
return w>x.w;//这里注意符号要为'>'
}
};
priority_queue<node>q;
//优先队列，其实这里一般使用一个pair，但为了方便理解所以用的结构体
inline void add(int u,int v,int w)
{
edge[++cnt].u=u;
//这句话对于此题不需要，但在缩点之类的问题还是有用的
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
//存储该点的下一条边
head[u]=cnt;
//更新目前该点的最后一条边（就是这一条边）
}
//链式前向星加边
void dijkstra()
{
for(int i=1;i<=n;i++)
{
dis[i]=INF;
}
dis[1]=0;
//赋初值
q.push((node){0,1});
while(!q.empty())
//堆为空即为所有点都更新
{
node x=q.top();
q.pop();
int u=x.now;
//记录堆顶（堆内最小的边）并将其弹出
if(vis[u]) continue;
//没有遍历过才需要遍历
vis[u]=1;
for(int i=head[u];i;i=edge[i].next)
//搜索堆顶所有连边
{
int v=edge[i].v;
if(dis[v]>dis[u]+edge[i].w)
{
dis[v]=dis[u]+edge[i].w;
//松弛操作
q.push((node){dis[v],v});
//把新遍历到的点加入堆中
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
add(x,y,1);
}
dijkstra();
if(dis[m]>n)
{
cout<<-1<<endl;
return 0;
}
cout<<dis[m]+1<<endl;
return 0;
}2. spfa
算法流程：
-
将除源点之外的所有的点当前距离初始化为无穷，并标记为未入队。源点的当前距离为
0 ，将源点入队。 -
取出队首
u ，遍历u 的所有出边，检查是否能更新所连接的点v 的当前距离。如果v 的当前距离被更新并且v 不在队中，则将v 入队。重复该操作直到队列为空。 -
检查是否存在负权环的方法为：记录一个点的入队次数，如果超过
V-1 次说明存在负权环，因为最短路径上除自身外至多V-1 个点，故一个点不可能被更新超过V-1 次。
时间复杂度
ACcode
//spfa
#include<bits/stdc++.h>
#define INF 1e9
#define maxn 1000005
using namespace std;
int n,m,s,num_edge=0;
int dis[maxn],vis[maxn],head[maxn];
struct Edge{
int next,to;
}edge[maxn]; //结构体表示静态邻接表
void add(int from,int to) //邻接表建图
{
edge[++num_edge].next=head[from];
edge[num_edge].to=to;
head[from]=num_edge;
}
void spfa()
{
queue<int> q; //spfa用队列，这里用了STL的标准队列
for(int i=1;i<=n;i++)
dis[i]=INF;
q.push(1);
dis[1]=1;
vis[1]=1; //第一个顶点入队，进行标记
while(!q.empty())
{
int u=q.front(); //取出队首
q.pop();
vis[u]=0; //出队标记
for(int i=head[u];i;i=edge[i].next) //邻接表遍历
{
int v=edge[i].to;
if(dis[v]>dis[u]+1) //如果有最短路就更改
{
dis[v]=dis[u]+1;
if(!vis[v]) //未入队则入队
{
vis[v]=1; //标记入队
q.push(v);
}
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
add(x,y); //建图，有向图连一次边就可以了
}
spfa(); //开始跑spfa
if(dis[m]!=INF) //存在
cout<<dis[m]<<endl;
else //不存在
cout<<-1<<endl;
return 0;
}