- 技术博客
- 【学习笔记】数据结构--最短路径问题（弗洛伊德和迪迦特斯拉）
前向星
void add_edge(int u
, int v
, int w
) {
edge
[cnt
].to
= v
;
edge
[cnt
].w
= w
;
edge
[cnt
].next
= head
[u
];
head
[u
] = cnt
++;
}
弗洛伊德（floyd）
void Floyd(MGraph
*mGraph
, int **iArrPath
) {
for (int i
= 1; i
<= mGraph
->iVertexCount
; i
++) {
for (int j
= 1; j
<= mGraph
->iVertexCount
; j
++) {
iArrPath
[i
][j
] = i
;
}
}
for (int k
= 1; k
<= mGraph
->iVertexCount
; k
++) {
for (int i
= 1; i
<= mGraph
->iVertexCount
; i
++) {
for (int j
= 1; j
<= mGraph
->iVertexCount
; j
++) {
if (mGraph
->edges
[i
][k
] + mGraph
->edges
[k
][j
] < mGraph
->edges
[i
][j
]) {
mGraph
->edges
[i
][j
] = mGraph
->edges
[i
][k
] + mGraph
->edges
[k
][j
];
iArrPath
[i
][j
] = iArrPath
[k
][j
];
}
}
}
}
}
迪迦特斯拉（DIJ）
void Dijkstra(ll start
) {
memset(dis
,0x3f,sizeof(dis
));
memset(vis
,0,sizeof(vis
));
dis
[start
]=0;
while(!q
.empty()) q
.pop();
q
.push(node(start
,0));
node tem
;
while(!q
.empty()) {
tem
=q
.top();
q
.pop();
long long u
=tem
.u
;
if(vis
[u
]) continue;
vis
[u
]=1;
for(long long i
=head
[u
]; i
!=-1; i
=A
[i
].nextt
) {
long long v
=A
[i
].to
;
long long w
=A
[i
].w
;
if(!vis
[v
]&&dis
[v
]>dis
[u
]+w
) {
dis
[v
]=dis
[u
]+w
;
q
.push(node(v
,dis
[v
]));
}
}
}
}
大模板
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<queue>
using namespace std
;
const int N
=1e3+100;
typedef long long ll
;
struct node
{
long long u
,w
;
node(long long _u
=0,long long _w
=0):u(_u
),w(_w
) {};
bool operator <(const node
&a
) const {
return w
>a
.w
;
}
};
struct Edge
{
ll to
,w
,nextt
;
} A
[1010000];
ll head
[N
],vis
[N
],dis
[N
];
ll tot
;
priority_queue
<node
>q
;
void addedge(ll from
,ll to
,ll w
) {
A
[tot
].to
=to
;
A
[tot
].w
=w
;
A
[tot
].nextt
=head
[from
];
head
[from
]=tot
++;
}
void Dijkstra(ll start
) {
memset(dis
,0x3f,sizeof(dis
));
memset(vis
,0,sizeof(vis
));
dis
[start
]=0;
while(!q
.empty()) q
.pop();
q
.push(node(start
,0));
node tem
;
while(!q
.empty()) {
tem
=q
.top();
q
.pop();
long long u
=tem
.u
;
if(vis
[u
]) continue;
vis
[u
]=1;
for(long long i
=head
[u
]; i
!=-1; i
=A
[i
].nextt
) {
long long v
=A
[i
].to
;
long long w
=A
[i
].w
;
if(!vis
[v
]&&dis
[v
]>dis
[u
]+w
) {
dis
[v
]=dis
[u
]+w
;
q
.push(node(v
,dis
[v
]));
}
}
}
}
void init() {
memset(head
,-1,sizeof(head
));
tot
=0;
}
ll
sovle1(int n
) {
Dijkstra(0);
ll cc
=0;
for(long long i
=1; i
<=n
; i
++) cc
=max(cc
,dis
[i
]);
return cc
;
}
ll
solve2(int s
,int n
) {
Dijkstra(s
);
ll cc
=0;
for(long long i
=1; i
<=n
; i
++) cc
=max(cc
,dis
[i
]);
return cc
;
}
int main() {
int T
;
scanf("%d",&T
);
while(T
--) {
init();
ll n
,m
,s
,k
,c
,t
,u
,v
,w
,x
;
scanf("%lld%lld%lld%lld%lld",&n
,&m
,&s
,&k
,&c
);
for(long long i
=1; i
<=k
; i
++) {
scanf("%lld",&x
);
addedge(0,x
,0);
}
for(long long i
=1; i
<=m
; i
++) {
scanf("%lld%lld%lld",&u
,&v
,&w
);
addedge(u
,v
,w
);
addedge(v
,u
,w
);
}
ll t1
=sovle1(n
);
ll t2
=solve2(s
,n
);
printf("%lld\n",t1
*c
>=t2
?t2
:t1
);
}
}
