Graph

abc143e.cpp

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

#define INF (ULLONG_MAX/3)
using ull = unsigned long long;
constexpr int MAXN = 3e2;
ull path[MAXN][MAXN];
ull tour[MAXN][MAXN];

int main(void) {
    int N, M, L;
    cin >> N >> M >> L;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) path[i][j] = 0;
            else path[i][j] = INF;
        }
    }
            
    for (int i = 0, u, v, w; i < M; i++) {
        cin >> u >> v >> w;
        path[u-1][v-1] = w;
        path[v-1][u-1] = w;
    }

    for (int k = 0; k < N; k++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                path[i][j] = min(path[i][j], path[i][k] + path[k][j]);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) tour[i][j] = 1;
            else if (path[i][j] <= L) tour[i][j] = 1;
            else tour[i][j] = INF;
        }
    }
    
    for (int k = 0; k < N; k++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                tour[i][j] = min(tour[i][j], tour[i][k] + tour[k][j]);

    int Q, s, t; cin >> Q;
    while (Q--) {
        cin >> s >> t;
        s--; t--;
        if (tour[s][t] == INF) cout << "-1\n";
        else cout << tour[s][t] - 1 << "\n";
    }
}

longest_path.cpp

// Source: https://atcoder.jp/contests/dp/tasks/dp_g
#include <iostream>
#include <vector>
using namespace std;

constexpr int MAXN = 1e5 + 1;
vector<int> adj[MAXN];
int in_degree[MAXN];
int dist[MAXN];
bool visited[MAXN];

void dfs(int s)
{
    visited[s] = true;
    for (int u : adj[s])
    {
        dist[u] = max(dist[u], 1 + dist[s]);
        in_degree[u]--;
        if (in_degree[u] == 0)
            dfs(u);
    }
}

int main(void)
{
    int N, M;
    cin >> N >> M;
    while (M--)
    {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        in_degree[y]++;
    }

    for (int i = 1; i <= N; i++)
        if (!visited[i] && in_degree[i] == 0)
            dfs(i);

    int ans = 0;
    for (int i = 1; i <= N; i++)
        ans = max(ans, dist[i]);
    cout << ans << "\n";
}