最短路

#include<bits/stdc++.h>
using namespace std;

const int MAXN=(int)1e3+10;
const int INF=0x3f3f3f3f;

int gra[MAXN][MAXN],dis[MAXN];
bool vis[MAXN];

void init(int n,int m);
void Dijkstra(int n,int st);

int main()
{
  int n,m,s;
  cin>>n>>m>>s;
  init(n,m);
  Dijkstra(n,s);
  for (int i=1;i<=n;i++) {
    printf("%d%c",dis[i]<INF ? dis[i] : -1," \n"[i==n]);
  }
  return 0;
}

void init(int n,int m)
{
  memset(gra,0x3f,sizeof(gra));
  for (int i=1;i<=n;i++) {
    gra[i][i]=0;
  }
  for (int i=0;i<m;i++) {
    int u,v,w;
    scanf("%d%d%d",&u,&v,&w);
    gra[u][v]=min(gra[u][v],w);
  }
}

void Dijkstra(int n,int st)
{
  for (int i=1;i<=n;i++) {
    dis[i]=gra[st][i];
  }
  for (int i=1;i<=n;i++) {
    int pos=-1;
    for (int j=1;j<=n;j++) {
      if (vis[j]==0 && (pos==-1 || dis[j]<dis[pos])) {
        pos=j;
      }
    }
    vis[pos]=1;
    for (int j=1;j<=n;j++) {
      dis[j]=min(dis[j],dis[pos]+gra[pos][j]);
    }
  }
}

#include<bits/stdc++.h>
using namespace std;

const int MAXN=(int)1e5+10;
const int MAXM=(int)2e5+10;
const int INF=0x3f3f3f3f;

struct Edge {
 int from,to,dist;
};
struct Node{
  int id,dist;
  bool operator<(const Node &t) const {
    return dist>t.dist;
  }
};

Edge e[MAXM];
vector<int> G[MAXN];
int dis[MAXN];
bool vis[MAXN];

void init(int m);
void Dijkstra(int n,int st);

int main()
{
  int n,m,st;
  cin>>n>>m>>st;
  init(m);
  Dijkstra(n,st);
  for (int i=1;i<=n;i++) {
    printf("%d%c",dis[i]," \n"[i==n]);
  }
  return 0;
}

void init(int m)
{
  for (int i=0;i<m;i++) {
    scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].dist);
    G[e[i].from].push_back(i);
  }
}

void Dijkstra(int n,int st)
{
  for (int i=1;i<=n;i++) {
    dis[i]=INF;
  }
  dis[st]=0;
  priority_queue<Node> pq;
  pq.push({st,0});

  while (!pq.empty()) {
    Node x=pq.top();
    pq.pop();
    int pos=x.id;
    if (vis[pos]) continue;
    vis[pos]=1;
    for (int i=0;i<G[pos].size();i++) {
      Edge &t=e[G[pos][i]];
      if (dis[pos]+t.dist<dis[t.to]) {
        dis[t.to]=dis[pos]+t.dist;
        pq.push({t.to,dis[t.to]});
      }
    }
  }
}