dijkstra

P3371 P4779

[[图论/链式前向星存图]] # 堆优化版 ：\(O(mlogm)\)

#include <bits/stdc++.h>
using namespace std;
//#define int long long
int n, m, s;
struct
{
    int v, w, next;
} a[200010];
bool vis[100010];
int dis[100010];
int cnt = 1;
int head[100010];
void add(int u, int v, int w)//链式前向星存图
{
    a[cnt].w = w;
    a[cnt].v = v;
    a[cnt].next = head[u];
    head[u] = cnt++;
}
#define pll pair<int, int>
priority_queue<pll, vector<pll>, greater<pll>> q;
void dijkstra(int s)
{
    memset(dis, 0x7f, sizeof dis);
    // for (int i = 1; i <= n; i++)
    //     dis[i] = INT_MAX;//弱化版还需要ll
    q.push({0, s});
    dis[s] = 0;
    while (!q.empty())
    {
        pll t = q.top();
        q.pop();
        int u = t.second;
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i; i = a[i].next)
        {
            int v = a[i].v;
            if (dis[v] > dis[u] + a[i].w)
            {
                dis[v] = dis[u] + a[i].w;
                q.push({dis[v], v});
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    dijkstra(s);
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
}

朴素写法 ：\(O(n^2)\)

#include<bits/stdc++.h>//O(n方)
using namespace std;
int mp[100][100];
int inf = 99999999;
int dis[100];
int book[100]={0};
int main() {
	int n, m;
	cin >> n >> m; //顶点数，边数
	int a, b, c;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				mp[i][j] = 0;
			else
				mp[i][j] = inf; //初始化
		}
	}
	for (int i = 1; i <= m; i++) {
		cin >> a >> b >> c;
		mp[a][b] = c; //建图
	}
	for (int i = 1; i <= n; i++) {
		dis[i] = mp[1][i];
	}
	book[1] = 1;
	//Dijkstra算法的核心部分
	int u;
	for (int i = 1; i <= n - 1; i++) {//找离原点最近的点 
		int minn = inf;
		for (int j = 1; j <= n; j++) {
			if ( book[j] == 0&&dis[j] < minn ) {
				minn = dis[j];
				u = j;
			}
		}
		book[u] = 1;
		for (int v = 1; v <= n; v++) {
			if (mp[u][v] < inf) {
				if (dis[v] > dis[u] + mp[u][v])
					dis[v] = dis[u] + mp[u][v];
			}
		}
	}
	cout<<dis[n]<<endl;
}