最短路径

#include <bits/stdc++.h>
using namespace std;
const int LP = 4500 + 1;
const long long INF = 0x7ffffffff;
long long n ,m ,x ,y ,w ,e[LP][LP];
int main()
{
  //freopen("Floyd.in" ,"r" ,stdin);
  //freopen("Floyd.out" ,"r" ,stdin);
  cin >> n >> m;
  memset(e ,INF ,sizeof(e));
  for (int i=1; i<=n; i++)
    for (int j=1; j<=n; j++)
      if (i == j) e[i][j] = 0;
      else e[i][j] = INF;
  for (int i=1; i<=m; i++)
  {
    cin >> x >> y >> w;
    e[y][x] = e[x][y] = min(e[x][y] ,w);
  }
  for (int k=1; k<=n; k++)
    for (int i=1; i<=n; i++)
      for (int j=1; j<=n; j++)
        e[i][j] = min(e[i][j] ,e[i][k] + e[k][j]);
  for (int i=1; i<=n; i++)
  {
    for (int j=1; j<=n; j++)
    {
      printf("%d " ,e[i][j]);
    }
    printf("\n");
  }
  //fclose(stdin);
  //fclose(stdout);
  return 0;
}

#include <bits/stdc++.h>
#define iosFast ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define Traverse(i, fa) for (int i = head[fa]; i; i = edge[i].next)
#define File(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout)
#define int long long
#define endl "\n"
using namespace std;
const int N = 1e4 + 10;
const int M = 5e5 + 10;
const int INF = INT_MAX;

int head[N], dis[N], tot = 1, n, m, s; 
bool vis[N];
struct Edge {
  int to;
  int next;
  int val;
} edge[M];

void Dijkstra(int fa) {
  for (int i = 1; i <= n; i++) dis[i] = INF;
  dis[fa] = 0;
  int Min, v;
  for (int i = 1; i <= n - 1; i++) {
    Min = INF;
    v = 0;
    for (int j = 1; j <= n; j++)
      if (!vis[j] && dis[j] < Min) {
        Min = dis[j];
        v = j;
      }
    if (v == 0) break;
    vis[v] = 1;
    Traverse(j, v) {
      int u = edge[j].to;
      if (!vis[u] && dis[v] + edge[j].val < dis[u])
      	dis[u] = dis[v] + edge[j].val;
    }
  }
}

inline void add (int u, int v, int w) {
  edge[tot].to = v;
  edge[tot].val = w;
  edge[tot].next = head[u];
  head[u] = tot++;
}

signed main () {
  iosFast;
  cin >> n >> m >> s;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    add (u, v, w);
  }
  Dijkstra(s);
  for (int i = 1; i <= n; i++)
    cout << dis[i] << " ";
  return 0;
}

#include <bits/stdc++.h>
#define iosFast ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define Traverse(i, fa) for (int i = head[fa]; i; i = edge[i].next)
#define File(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout)
#define int long long
#define endl "\n"
using namespace std;
const int N = 1e4 + 10;
const int M = 5e5 + 10;
const int INF = INT_MAX;
int head[N];

struct Edge {
  int to, val;
  int next;
} edge[M];

inline void addedge(int u, int v, int w, int tot) {
  edge[tot].to = v;
  edge[tot].next = head[u];
  edge[tot].val = w;
  head[u] = tot;
}

int dis[N];
int n, m;

void BellmanFord(int s) {
	for (int i = 1; i <= n; i++) dis[i] = INF;
	dis[s] = 0;
	for (int i = 1; i <= n - 1; i++) {
		for (int j = 1; j <= n; j++) {
			if (dis[j] == INF) continue;
			Traverse(k, j) {
				if (edge[k].val != INF && dis[edge[k].to] > dis[j] + edge[k].val)
					dis[edge[k].to] = dis[j] + edge[k].val;
			}
		}
	}
}

signed main() {
  int s;
  cin >> n >> m >> s;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    addedge(u, v, w, i);
  }
  BellmanFord(s);
  for (int i = 1; i <= n; i++) cout << dis[i] << " ";
  return 0;
}