代码随想录第60天

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int bian= sc.nextInt();
        int [][]map=new int[n+1][n+1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(map[i],Integer.MAX_VALUE);
        }

        for (int i = 0; i < bian; i++) {
            int s1=sc.nextInt(),s2=sc.nextInt(),s3=sc.nextInt();
            map[s1][s2]=s3;
        }
        int[] res = new int[n + 1];
        Arrays.fill(res,Integer.MAX_VALUE);
        res[1]=0;
        for(int k=0;k<n;k++){
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if(map[i][j]!=Integer.MAX_VALUE&&res[i]!=Integer.MAX_VALUE){
                    if(res[i]+map[i][j]<res[j]){
                        res[j]=res[i]+map[i][j];
                    }
                }
            }
        }}
        System.out.println(res[n]==Integer.MAX_VALUE?"unconnected":res[n]);
    }
}

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

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid;

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid.push_back({p1, p2, val});

    }
    int start = 1;  // 起点
    int end = n;    // 终点

    vector<int> minDist(n + 1 , INT_MAX/2);
    minDist[start] = 0;
    bool flag = false;
    for (int i = 1; i <= n; i++) {
        for (vector<int> &f : grid) {
            int from = f[0];
            int to = f[1];
            int price = f[2];
            //cout << f[0] << " " << f[1] << " " << f[2] << endl;
            if (i < n) {
                if (minDist[to] > minDist[from] + price && minDist[from] != INT_MAX/2) minDist[to] = minDist[from] + price;
            } else { // 多加一次松弛判断负数环
                if (minDist[to] > minDist[from] + price && minDist[from] != INT_MAX/2) flag = true;

            }
        }

    }

    if (flag) cout << "circle" << endl;
    else if (minDist[end] == INT_MAX/2) {
        cout << "unconnected" << endl;
    } else {
        cout << minDist[end] << endl;
    }
}

#include <iostream>
#include <cstring>
using namespace std;
const int N=1e4+7;
const int inf=0x3f3f3f3f;
struct node{
    int a,b,c;
}e[N];
int dist[N],back[N];
int n,m,st,ed,k;

void bf(){
    for(int i=1;i<=n;i++)dist[i]=inf;
    dist[st]=0;
    for(int i=0;i<k;i++){
        for(int i=1;i<=n;i++)back[i]=dist[i];
        for(int j=1;j<=m;j++){
            int u=e[j].a;
            int v=e[j].b;
            int z=e[j].c;
            dist[v]=min(dist[v],back[u]+z);
        }
    }
    return;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        e[i]={a,b,c};
    }
    cin>>st>>ed>>k;
    k+=1;
    bf();
    if(dist[ed]>=0x3f3f3f3f/2){
        cout<<"unreachable";
        return 0;
    }
    cout<<dist[ed];
    return 0;
}