signed

QiShunwang

“诚信为本、客户至上”

最短路dijkstra模板

2020/8/20 10:47:47   来源:
typedef long long LL;
const LL INF = 0x3f3f3f3f;
LL cost[2010][2010]; //两个之间没有边,值为INF,这个操作是在输入边之前完成
LL d[2010]; //d[i]表示从源点到第i点的最短距离
bool used[2010]; //判断下标为i的点是否使用
LL V,E;//V为点的个数,E为边的个数
void dijkstra(LL s) //s是源点
{
	memset(d, INF, sizeof(d));  //初始化
	memset(used, 0, sizeof(used));//初始化
	d[s] = 0; //源点与自身的距离为0
	while (1)
	{
		LL v = -1; //判断是否还存在尚未使用的点
		for (LL u = 0; u < V; u++)
		{
			if (!used[u] && (v == -1 || d[u] < d[v])) v = u; //从尚未使用过的顶点中选择一个距离最小的顶点
		}
		if (v == -1) break; //全都使用了,退出
		used[v] = 1; //标记为使用了
		for (LL u = 0; u < V; u++) //遍历所有点,更新单源最短路
		{
			d[u] = min(d[u], d[v] + cost[v][u]);
		}
	}
}

顺便贴一道dij裸体
注意重边,以及输入的先是边再是点
AC代码

#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f;
LL cost[2010][2010];
LL d[2010];
bool used[2010];
LL V,E;
void dijkstra(LL s)
{
	memset(d, INF, sizeof(d));
	memset(used, 0, sizeof(used));
	d[s] = 0;
	while (1)
	{
		LL v = -1;
		for (LL u = 0; u < V; u++)
		{
			if (!used[u] && (v == -1 || d[u] < d[v])) v = u;
		}
		if (v == -1) break;
		used[v] = 1;
		for (LL u = 0; u < V; u++)
		{
			d[u] = min(d[u], d[v] + cost[v][u]);
		}
	}
}
int main()
{
	IOS;
	cin >> E >> V;
	memset(cost, INF, sizeof(cost));
	for (LL i = 0; i < E; i++)
	{
		LL a, b,w;
		cin >> a >> b>>w;
		cost[a-1][b-1] =cost[b-1][a-1]=min(cost[a-1][b-1],w);
	}
	dijkstra(0);
	cout << d[V-1] << endl;
}