leetcode 743. Network Delay Time

Posted on | In , |

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Note:

N will be in the range [1, 100].

K will be in the range [1, N].

The length of times will be in the range [1, 6000].

All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
struct node{
    int num;
    int value;
    node(int nn,int vv):num(nn),value(vv){}
    bool operator <(node p)const{
        return value>p.value;
    }
};
class Solution {
public:
    int dis[100];
    int vis[100];
    //vector<vector<int> > g;
    map<int,vector<node>> g;
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        for(int i=0;i<times.size();i++){
            
            g[times[i][0]].push_back(node(times[i][1],times[i][2]));
            
        }
         for(int i=1;i<=N;i++){
            dis[i]=1e8;
         }
        for(int j=0;j<g[K].size();j++){
        dis[g[K][j].num]=g[K][j].value;
        }
            priority_queue<node> pq;
        pq.push(node(K,0));
        dis[K]=0;  
        while(!pq.empty()){
            node t=pq.top();
            pq.pop();
            int index=t.num;
            int cost=t.value;
            if(vis[index]) continue;
            vis[index]=1;//!!
            for(int j=0;j<g[index].size();j++){
                if(cost+g[index][j].value<dis[g[index][j].num])
                {
                dis[g[index][j].num]=cost+g[index][j].value;
            
                    //
                }
                pq.push(node(g[index][j].num, dis[g[index][j].num]));//!!写成dis[j]错误 dis[g[index][j].num]是取出的节点的编号和距离
            }

        }
        
        
        
        int ans=0;
            
        for(int i=1;i<=N;i++)
        {
            if(dis[i]==1e8) return -1;
                        ans=max(ans,dis[i]);
        }

     
         return ans;
        
    }
};