有一个分布式服务集群,集群内含有 N 个服务节点,分别标记为 1 到 N。
给予一个列表 times,表示消息从两个节点间有向传递需要的时间。 times[i] = (s, d, t),其中 s 表示发出消息的源节点,d 表示接收到消息的目标节点, t 表示信息有向传递的时间。
现在 K 节点发送了一个信号,请问至少需要多少秒才能使所有的服务节点都收到该消息?如果消息不能传递给集群内全部节点,则返回-1。
第一行:列表 times。分布式服务集群的图,图的结构为二维数组。例如: [[2,1,1],[2,3,1],[3,4,1]] ,表示集群4个节点,2到1的时间为1,2到3的时间为1,3到4的时间为1;
第二行:N值
第三行:K值
范围约束:
1. N 的范围在 [1, 100] 之间。
2. K 的范围在 [1, N] 之间。
3. times 的长度在 [1, 6000] 之间。
4. 所有的边 times[i] = (s, d, t) 都有 1 <= s, d <= N 且 1 <= t <= 100。
至少需要多少秒才能使所有的服务节点都收到该消息?如果消息不能传递给集群内全部节点,则返回-1
[[2,1,1],[2,3,1],[3,4,1]] 4 2
2
图可能存在重边或自环
/*
单源最短路径
无向(有环)图无负权,考虑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; }
times = eval(input()) n = int(input()) k = int(input()) A = [[] for _ in range(n + 1)] for s, d, t in times: A[s].append((d, t)) # 初始化起点到所有节点的距离 dis = [float("inf")]*(n + 1) dis[k] = 0 # 先将起点加入队列 queue = [k] while queue: s = queue.pop(0) for d, t in A[s]: if dis[d] > dis[s] + t: dis[d] = dis[s] + t queue.append(d) # 发送到所有节点的时间取决于发送到最远节点的用时 max_dis = max(dis[1:]) # 第一个节点dis[0]没有使用,不用于计算最大值 print(-1 if max_dis == float("inf") else max_dis)
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); } }发一个容易看得懂的
from collections import defaultdict as dt def find(dist,k,n): d=dt(int) s={k:0} while len(s)<n: tmp=float('inf') ind=tar=None for i in s: if i not in dist: continue while d[i]<len(dist[i]) and dist[i][d[i]][0] in s: d[i]+=1 if d[i]==len(dist[i]): continue if s[i]+dist[i][d[i]][1]<tmp: tmp=dist[i][d[i]][1]+s[i] tar=dist[i][d[i]][0] ind=i if not ind:break d[ind]+=1 s[tar]=tmp if len(s)==n: print(max(s.values())) else:print(-1) dist={} d=eval(input()) for i in d: if i[0]==i[1]:continue if i[0] not in dist: dist[i[0]]=[i[1:]] else:dist[i[0]].append(i[1:]) for i in dist: dist[i].sort(key=lambda i:i[1]) n=int(input()) k=int(input()) find(dist,k,n)
#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; }