以热浪为样题

floyd:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf = 2147483;
void read(int &a)
{
	a = 0;
	char s = getchar();
	while (s < '0' || s > '9')
		s = getchar();
	while (s >= '0' && s <= '9')
	{
		a *= 10;
		a += s - '0';
		s = getchar();
	}
}
int map[2501][2501];
void floyd(int t)
{
	for (int k = 1; k <= t; k++)
	{
		for (int i = 1; i <= t; i++)
		{
			if (k == i)
				continue;
			for (int j = 1; j <= i; j++)
			{
				if (j == i || j == k)
					continue;
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
                map[j][i] = map[i][j];
			}
		}
	}
}
int main()
{
	int t, c, ts, te;
	cin >> t >> c >> ts >> te;
	if (ts > te)
		swap(ts, te);
	for (int i = 1; i <= t; i++)
		for (int j = 1; j <= t; j++)
			map[i][j] = inf;
	for (int i = 1; i <= c; i++)
	{
		int f, t, d;
		read(f);
		read(t);
		read(d);
		map[f][t] = min(map[f][t], d);
		map[t][f] = min(map[t][f], d);
	}
	floyd(t);
	cout << map[ts][te];
	return 0;
}

dijkstra(堆优化):

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int first[233333], next[233333], d[233333], tot = 0;
bool used[233333];
struct edge
{
	int from, to, cost;
}es[233333];
struct love
{
	int num, d;
};
bool operator < (love a, love b)
{
	return a.d > b.d;
}
priority_queue <love> q;
void init()
{
	memset(first, -1, sizeof(first));
	memset(d, 0x3f, sizeof(d));
	tot = 0;
}
void build(int f, int t, int d)
{
	es[++tot] = (edge){f, t, d};
	next[tot] = first[f];
	first[f] = tot;
}
void dijkstra(int s)
{
	q.push((love){s, 0});
	d[s] = 0;
	used[s] = 1;
	while (!q.empty())
	{
		int now = q.top().num;
		int dist = q.top().d;
		q.pop();
		used[now] = 1;
		for (int i = first[now]; i != -1; i = next[i])
		{
			int v = es[i].to;
			if (d[v] > d[now] + es[i].cost)
			{
				d[v] = d[now] + es[i].cost;
				if (!used[v])
				{
					q.push((love){v, d[v]});
                                        used[v] = 1;
				}
			}
		}
	}
}
int main()
{
	init();
	int t, c, ts, te;
	cin >> t >> c >> ts >> te;
	for (int i = 1; i <= c; i++)
	{
		int f, t, d;
		scanf("%d%d%d", &f, &t, &d);
		build (f, t, d);
		build (t, f, d);
	}
	dijkstra(ts);
	cout << d[te];
	return 0;
}

spfa；

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int first[233333], next[233333], d[233333], tot = 0;
bool used[233333];
struct edge
{
	int from, to, cost;
}es[233333];
queue <int> q;
void init()
{
	memset(first, -1, sizeof(first));
	memset(d, 0x3f, sizeof(d));
	tot = 0;
}
void build(int f, int t, int d)
{
	es[++tot] = (edge){f, t, d};
	next[tot] = first[f];
	first[f] = tot;
}
void spfa(int s)
{
	used[s] = 1;
	d[s] = 0;
	q.push(s);
	while (!q.empty())
	{
		int u = q.front();
		used[u] = 0;
		q.pop();
		for (int i = first[u]; i != -1; i = next[i])
		{
			int v = es[i].to;
			if (d[v] > d[u] + es[i].cost)
			{
				d[v] = d[u] + es[i].cost;
				if (!used[v])
				{
					used[v] = 1;
					q.push(v);
				}
			}
		}
	}
}
int main()
{
	init();
	int t, c, ts, te;
	cin >> t >> c >> ts >> te;;
	for (int i = 1; i <= c; i++)
	{
		int f, t, d;
		scanf("%d%d%d", &f, &t, &d);
		build (f, t, d);
		build (t, f, d);
	}
	spfa(ts);
	cout << d[te];
	return 0;
}