517pj训练-3

迪杰斯特拉

也是比较好理解的最短路算法 朴素稳定O(n方)

得去解决一下latex的问题

先把所有的点(除了起点)标成不确定

每次扫一遍,从所有确定的点延伸出去一条,替换成最小值,选其中最小的,标记成确定的,直到全确定

例题 T1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define inf 10000000
using namespace std;
int n,m,a,b,c;
int val[1010][1010];
int dis[1010];
int vis[1010];
vector<int> g[1010];
void dij()
{
for(int i=1;i<=n;i++)dis[i]=val[1][i];
vis[1]=1;
for(int i=1;i<n;i++)
{
int minn=inf;
int id=-1;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&dis[j]<minn)
{
minn=dis[j];
id=j;
}
}
vis[id]=1;
for(int j=0;j<g[id].size();j++)
{
int idd=g[id][j];
if(!vis[idd]&&dis[id]+val[id][idd]<dis[idd])
{
dis[idd]=dis[id]+val[id][idd];
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
if(i==j)val[i][j]=0;
else val[i][j]=val[j][i]=inf;
}
while(m--)
{
cin>>a>>b>>c;
g[a].push_back(b);
g[b].push_back(a);
val[a][b]=min(val[a][b],c);
val[b][a]=min(val[a][b],c);
}
dij();
cout<<dis[n]<<endl;
}

重要:

如何优化?

1.空间优化 邻接表

2.时间优化 堆

因为每次找最小的都要全搜一遍,所以浪费了,堆优化完美解决

例题 T3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
#define inf 2147483647
#define ll long long
using namespace std;
int head[100005],tot,n,m,s,x,y,z,vis[100005],t;
ll d[100005];
struct hate
{
int to,val,nxt;
}e[200005];
void add(int a,int b,int c)
{
e[++tot].to=b,e[tot].nxt=head[a],head[a]=tot,e[tot].val=c;
}
struct node
{
int d;
int pos;
bool operator <( const node &x)const
{
return x.d<d;
}
};
priority_queue<node> q;
void diji()
{
for(int i=1;i<=n;i++)d[i]=inf;
d[s]=0;
ll id=s;
q.push((node){0,s});
while(q.size())
{
node a=q.top();
q.pop();
ll id=a.pos,minn=a.d;
if(vis[id])continue;
vis[id]=1;
for(int j=head[id];j!=0;j=e[j].nxt)
{
int idd=e[j].to;
if(!vis[idd]&&d[idd]>d[id]+e[j].val)
{
d[idd]=d[id]+e[j].val;
if(!vis[idd])
{
q.push((node){d[idd],idd});
}
}
}
}
}
int main()
{
cin>>n>>m>>s>>t;
for(int i=0;i<m;i++)
{
cin>>x>>y>>z;
add(x,y,z);
}
diji();
if(d[t]==inf)cout<<-1<<endl;
else cout<<d[t]<<endl;
}

由于我tcl,所以讲不清楚,放一个咕咕日报好了:

这玩意