PP4885 网的邻接矩阵1（基础）

这道题和"网的邻接矩阵2"输入格式完全一样，但图的类型不同：那一题是无向的网，这一题是"有向"的网。一字之差，建图的方法就完全不同了。

解题思路

第一步，抓住有向网的关键。 有向网里的边有方向：x y w 表示只能从 x 走到 y，权值是 w，不能反过来从 y 走到 x。所以在邻接矩阵里只填 a[x][y]=w，a[y][x] 要保持 999。

第二步，初始化矩阵。 和上一题一样，先把整个矩阵全部填成 999，表示一开始任意两个结点之间都没有边，自己到自己也没有边。

第三步，读边写入。 每读一条 x y w，只执行 a[x][y]=w 这一句赋值。例如样例 2 1 2，只在 a[2][1] 填 2。看样例输出第二行是 2 999 999 999，说明结点 2 能走到 1（权值 2），但结点 1 走到 2 没有路（第一行的第二个位置是 999）。这就是有向和无向最明显的区别。

第四步，输出矩阵。 逐行输出，行内数字用空格隔开。样例第一行 999 999 999 8，说明结点 1 只向外走了一条边 1→4，权值 8。

第五步，总结记忆方法。 无向网写两次（x→y 和 y→x），有向网写一次（只写 x→y）。做题时先看清题目是"有向"还是"无向"，再决定要不要补反向赋值。

参考代码

// 输入有向网的边和权值，建立邻接矩阵并输出，无边处用999
#include <iostream>
using namespace std;

int a[505][505];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = 999; // 初始全部无边
    for (int k = 0; k < m; k++) {
        int x, y, w;
        cin >> x >> y >> w;
        a[x][y] = w; // 有向网，只设置起点到终点
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (j > 1) cout << " ";
            cout << a[i][j];
        }
        cout << endl;
    }
    return 0;
}

复杂度分析

复杂度分析：初始化矩阵 O(n²)，读边 O(m)，输出 O(n²)，总时间复杂度 O(n²)，空间复杂度 O(n²)。n 是结点数，规模小，轻松通过。