最短路径算法(跟新SPFA,Ford)

时间:2022-10-21 15:11:46

//以城市路为蓝本介绍算法

1381:城市路(Dijkstra)

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 4517     通过数: 1306

【题目描述】

罗老师被邀请参加一个舞会,是在城市n,而罗老师当前所处的城市为1,附近还有很多城市2~n-1,有些城市之间没有直接相连的路,有些城市之间有直接相连的路,这些路都是双向的,当然也可能有多条。

现在给出直接相邻城市的路长度,罗老师想知道从城市1到城市n,最短多少距离。

【输入】

输入n, m,表示n个城市和m条路;

接下来m行,每行a b c, 表示城市a与城市b有长度为c的路。

【输出】

输出1到n的最短路。如果1到达不了n,就输出-1。

【输入样例】

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

【输出样例】

90

【提示】

【数据规模和约定】

1≤n≤2000

1≤m≤10000

0≤c≤10000

【来源】

No

SPAF:

#include<bits/stdc++.h>
using namespace std;
struct node
{
int next,to,val;
}edge[];
int h[],num=;
void add_edge(int from,int to,int val)
{
num++;
edge[num].to=to;
edge[num].val=val;
edge[num].next=h[from];
h[from]=num;
}
int dis[];
bool used[];
int Q[],head,tail;
int main()
{
int n,m;
cin>>n>>m; for(int i=;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add_edge(x,y,z);
add_edge(y,x,z);
} memset(dis,0x3f,sizeof(dis));
dis[]=;
Q[]=;head=;tail=;used[]=true;
while(head<=tail)
{
//1.取出头结点
int from=Q[head];
head++;
used[from]=false;
//2.拓展新的尾结点
for(int j=h[from];j!=;j=edge[j].next)
{
int to=edge[j].to;
int val=edge[j].val;
if(dis[to]>dis[from]+val)
{
dis[to]=dis[from]+val;
if(!used[to])
{
tail++;
Q[tail]=to;
used[to]=true;
}
}
} } if(dis[n]==0x3f3f3f3f)
cout<<-;
else
cout<<dis[n]; return ;
}

Ford:

#include<bits/stdc++.h>
using namespace std;
struct node
{
int from,to,val;
}edge[];
int num;
void add_edge(int from,int to,int val)
{
num++;
edge[num].from=from;
edge[num].to=to;
edge[num].val=val;
}
int dis[];
int main()
{
int n,m;
cin>>n>>m;
for(int i=;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add_edge(x,y,z);
}
memset(dis,0x3f,sizeof(dis));
dis[]=; for(int i=;i<=n;i++)
{
for(int j=;j<=num;j++)
{
int from=edge[j].from;
int to=edge[j].to;
int val=edge[j].val;
dis[to]=min(dis[to],dis[from]+val);
dis[from]=min(dis[from],dis[to]+val);
}
} if(dis[n]==0x3f3f3f3f)
cout<<-;
else
cout<<dis[n];
return ;
}

//~~可能并不能过。。。。~~