分布式集群消息传递

/*
单源最短路径
无向(有环)图无负权，考虑Dijkstra算法，适用于本题 
有负权，考虑 Bellman-Ford算法（SPFA算法）
有向图无环图，直接拓扑排序 
*/
#include <bits/stdc++.h>
using namespace std;
const int Ni = 101;
struct node {
    int point, value;
    node(int a, int b) // 构造
    {
        point = a;
        value = b;
    }
    // 重载<操作符
    bool operator<(const node &a) const
    {
        // 对小于运算符进行重载，如果两个值相等，那么继续判断point，如果不等，则返回false
        if (value == a.value) {
            return a.point < point;
        } else {
            return a.value < value;
        }
    }
};
vector<node> e[Ni];
int dis[Ni], n;
priority_queue<node> q;
void dijkstra();
int main()
{
    int a, b, c, k;
    char s;
    getchar();
    while(getchar() == '[') {
        scanf("%d%c%d%c%d%c%c", &a, &s, &b, &s, &c, &s, &s);
        e[a].push_back(node(b, c));
// e[b].push_back(node(a, c));  // 无向图
    }
    scanf("%d%d", &n, &k);

    memset(dis, 0x7f, sizeof(dis));
    dis[k] = 0;
    // 优先队列，队头元素最大，要求最小且类型为struct需要重载<运算符
    q.push(node(k, dis[k]));
    dijkstra();

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dis[i]);
    }
    if(ans == 0x7f7f7f7f) ans = -1;
    printf("%d\n", ans);
    system("pause");
    return 0;
}
void dijkstra()
{
    while (!q.empty()) {
        node x = q.top();
        q.pop();
        for (int i = 0; i < e[x.point].size(); i++) {
            node y = e[x.point][i];
            // 核心思想：更新估算距离，松弛
            if (dis[y.point] > dis[x.point] + y.value) {
                dis[y.point] = dis[x.point] + y.value;
                q.push(node(y.point, dis[y.point]));
            }
        }
    }
}

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

int N, K, G[101][101], dis[101];
bool vis[101];

void dijkstra(int s){
    dis[s] = 0;
    for(int i=0;i<N;i++){
        int k=0, Min=INT_MAX;
        for(int j=1;j<=N;j++){
            if(!vis[j] && dis[j]<Min){
                Min = dis[j];
                k = j;
            }
        }
        if(k==0)
            break;
        vis[k] = true;
        for(int v=1;v<=N;v++){
            if(!vis[v] && G[k][v]!=INT_MAX && dis[v]>dis[k]+G[k][v])
                dis[v] = dis[k] + G[k][v];
        }
    }
}

int main(){
    int s, d, t, Max=0;
    memset(vis, false, sizeof(vis));
    for(int i=0;i<101;i++){
        dis[i] = INT_MAX;
        for(int j=0;j<101;j++){
            if(i==j)
                G[i][j] = 0;
            else
                G[i][j] = INT_MAX;
        }
    }
    char c = getchar();
    while(c!=']'){
        scanf("[%d,%d,%d]", &s, &d, &t);
        if(s!=d && t<G[s][d])
            G[s][d] = t;
        c = getchar();
    }
    scanf("%d%d", &N, &K);
    dijkstra(K);
    for(int i=1;i<=N;i++)
        Max = max(Max, dis[i]);
    if(Max==INT_MAX)
        printf("-1\n");
    else
        printf("%d\n", Max);
    return 0;
}

import java.util.*;


/**
 * @author lizifan 695199262@qq.com
 * @since 2019/10/22 16:32
 */
public class Main {

    static class Entry {
        Node node;
        int dis;

        Entry(Node node, int dis) {
            this.node = node;
            this.dis = dis;
        }
    }

    static class Node {
        final int id;
        final List<Entry> nodes = new LinkedList<>();

        Node(int id) {
            this.id = id;
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int N = sc.nextInt();
        int k = sc.nextInt();

        String[] s = str.split("[^0-9]+");

        Map<Integer, Node> map = new HashMap<>(N, 1);

        for (int i = 1; i < s.length; i += 3) {
            int a = Integer.parseInt(s[i]);
            int b = Integer.parseInt(s[i + 1]);
            int d = Integer.parseInt(s[i + 2]);

            Node an = map.get(a);
            if(an == null) {
                an = new Node(a);
                map.put(a, an);
            }

            Node bn = map.get(b);
            if(bn == null) {
                bn = new Node(b);
                map.put(b, bn);
            }

            an.nodes.add(new Entry(bn, d));
        }


        int[] ans = new int[N + 1];
        Arrays.fill(ans, Integer.MAX_VALUE);

        Node start = map.get(k);
        if(start == null) {
            System.out.println(-1);
            return;
        }

        Queue<Node> queue = new LinkedList<>();
        Queue<Integer> wayQueue = new LinkedList<>();
        queue.offer(start);
        wayQueue.offer(0);
        ans[k] = 0;

        while (!queue.isEmpty()) {
            Node n = queue.poll();
            int way = wayQueue.poll();
            n.nodes.forEach(e -> {
                Node nd = e.node;
                int w = e.dis;
                if(way + w < ans[nd.id]) {
                    ans[nd.id] = way + w;
                    queue.offer(nd);
                    wayQueue.offer(way + w);
                }
            });
        }

        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= N; i++) {
            max = Math.max(ans[i], max);
        }

        System.out.println(max == Integer.MAX_VALUE ? "-1" : max);
    }
}

import java.util.*;

// Dijkstra：单源最短路径
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.next();
        int n = in.nextInt(), k = in.nextInt();
        List<List<int[]>> g = new ArrayList<>(); // 邻接表
        for (int i = 0; i <= n; i++) {
            g.add(new ArrayList<>());
        }
        line = line.substring(2, line.length() - 2); // 处理输入
        String[] sp = line.split("\\],\\["); // 去掉首尾[[ ]], 中间可以用],[分割
        for (String str : sp) {
            String[] spp =  str.split(",");
            int s = Integer.parseInt(spp[0]);
            int d = Integer.parseInt(spp[1]);
            int t = Integer.parseInt(spp[2]);
            g.get(s).add(new int[] {d, t}); // 有向图
            // g.get(d).add(new int[] {s, t});
        }

        int[] dist = new int[n + 1]; // k点到其他点的距离
        int INF = Integer.MAX_VALUE >> 1;
        Arrays.fill(dist, INF);
        dist[k] = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b)->a[1] - b[1]);
        queue.offer(new int[] {k, 0});
        while (!queue.isEmpty()) {
            int[] a = queue.poll();
            int s = a[0], dis = a[1];
            if (dis > dist[s]) continue;

            for (int[] b : g.get(s)) {
                int d = b[0], t = b[1];
                int newDis = dis + t;
                if (newDis < dist[d]) {
                    dist[d] = newDis;
                    b[1] = newDis;
                    queue.offer(b);
                }
            }
        }

        int max = -1;
        for (int i = 1; i <= n; i++) { // k到其他点的最长距离
            if (dist[i] == INF) {
                max = -1;
                break;
            }
            max = Math.max(dist[i], max);
        }
        System.out.println(max);
    }
}

#include<bits/stdc++.h>
using namespace std;
struct cmp{
        bool operator()(pair<int,int>& a,pair<int,int>& b)
        {
            return a.first > b.first; // 小顶堆
        }
    };
int main()
{
    // 堆优化dijsktra 单源最短路径
    int a,b,c;
    char s;
    int N,K;
    getchar();
    vector<vector<int>>times;
    while(getchar()=='[')
    {
        scanf("%d%c%d%c%d%c%c",&a,&s,&b,&s,&c,&s,&s);
        vector<int>tmp = {a,b,c};
        times.push_back(tmp);
    }
    cin>>N>>K;
       // first是距离，second是目标点 
        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>pq;
        // 源点到各顶点的距离
        vector<int>d(N+1,INT_MAX);

        d[K] = 0;

        // 起点入队
        pq.push(make_pair(0,K));

        while(!pq.empty())
        {
            // it为连接已访问点和未访问点的最小边
            auto it = pq.top(); pq.pop();
            // 如果这条边的长度已经比最短路径还大，则不可能缩短路径
            // 说明这个pair保持的数据过时，最短路径值已经更新过
            if(it.first>d[it.second]) continue;
            for(int i=0;i<times.size();++i)
            {
                if(times[i][0]==it.second)
                {
                    int v = times[i][1];
                    int w = times[i][2] + it.first;
                    if(d[v]>w)
                    {
                        pq.push(make_pair(w,v));
                        d[v] = w;
                    }

                }
            }
        }

        int ans = INT_MIN;
        for(int i=1;i<=N;++i)
        {
            if(d[i]==INT_MAX){
                cout<<-1;return 0;
            }
            ans = max(ans,d[i]);
        }
        cout<<ans<<endl;
    return 0;
}