C++ 蓝桥云课代码练习

代码一，蓝桥公园，代码见下：

#include <iostream>
#include <cstring>
using namespace std;

#define maxn 401

long long mat[maxn][maxn];

int main()
{
  int n, m, q;
  cin >> n >> m >> q;
  memset(mat, -1, sizeof(mat));

  for(int i=1; i<=n; ++i){
    mat[i][i] = 0;
  }

  while(m--){
    int u, v, w;
    cin >> u >> v >> w;
    if(mat[u][v] == -1 || w < mat[u][v]){
      mat[u][v] = w;
    }
    if(mat[v][u] == -1 || w < mat[v][u]){
      mat[v][u] = w;
    }

  }

  for(int k=1; k<= n; ++k){
    for(int i=1; i<=n; ++i){
      if(i == k) continue;
      if(mat[i][k] == -1){
        continue;
      }
      for(int j=1; j<=n; ++j){
        if(j == k || j == i) continue;
        if(mat[k][j] == -1){
          continue;
        }
        if(mat[i][k] + mat[k][j] < mat[i][j] || mat[i][j] == -1){
          mat[i][j] = mat[i][k] + mat[k][j];
        }

      }
    }
  }
  while(q--){
    int u, v;
    cin >> u >> v;
    cout << mat[u][v] << endl;;
  }
  // 请在此输入您的代码
  return 0;
}

代码二，对应蓝桥王国，代码见下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

#define maxn 300005

struct Edge{
  int v;
  long long w;

  Edge(){}
  Edge(int _v, long long _w){
    v = _v;
    w = _w;
  }
};

vector<Edge> edge[maxn];
long long dist[maxn];
int main()
{
  int n, m;
  cin >> n >> m;
  memset(dist, -1, sizeof(dist));
  while(m--){
    int u, v, w;
    cin >> u >> v >> w;
    edge[u].push_back(Edge(v, w));
  }
  dist[1] = 0;
  queue<Edge> q;
  q.push(Edge(1, dist[1]));

  while(!q.empty()){
    Edge x = q.front();
    q.pop();
    int u = x.v;
    for(int i=0; i < edge[u].size(); ++i){
      int v = edge[u][i].v;
      long long d = edge[u][i].w;
      if(dist[v] == -1 || x.w + d < dist[v]){
        dist[v] = x.w + d;
        q.push(Edge(v, dist[v]));
      }
    }
  }
  for(int i=1; i<=n; ++i){
    if(i!=1){
      cout << ' ';
    }
    cout << dist[i];
  }

  // 请在此输入您的代码
  return 0;
}