<p>You are given a network of <code>n</code> nodes, labeled from <code>1</code> to <code>n</code>. You are also given <code>times</code>, a list of travel times as directed edges <code>times[i] = (u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>)</code>, where <code>u<sub>i</sub></code> is the source node, <code>v<sub>i</sub></code> is the target node, and <code>w<sub>i</sub></code> is the time it takes for a signal to travel from source to target.</p>

<p>We will send a signal from a given node <code>k</code>. Return <em>the <strong>minimum</strong> time it takes for all the</em> <code>n</code> <em>nodes to receive the signal</em>. If it is impossible for all the <code>n</code> nodes to receive the signal, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/05/23/931_example_1.png" style="width: 217px; height: 239px;" />
<pre>
<strong>Input:</strong> times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> times = [[1,2,1]], n = 2, k = 1
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> times = [[1,2,1]], n = 2, k = 2
<strong>Output:</strong> -1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= times.length &lt;= 6000</code></li>
	<li><code>times[i].length == 3</code></li>
	<li><code>1 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n</code></li>
	<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>
	<li><code>0 &lt;= w<sub>i</sub> &lt;= 100</code></li>
	<li>All the pairs <code>(u<sub>i</sub>, v<sub>i</sub>)</code> are <strong>unique</strong>. (i.e., no multiple edges.)</li>
</ul>

#define pii pair<int,int>
class Solution {
public:
    int inf=10000;
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<int> adj[n+2];
        vector<bool> vis(n+2, false);
        int mat[n+5][n+5];
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++) mat[i][j]=inf;
        }
        for(int i=0; i<times.size();i++){
                adj[times[i][0]].push_back(times[i][1]);
                mat[times[i][0]][times[i][1]] = times[i][2];
        }
        for(int i=0; i<n;i++) mat[i+1][i+1]=0;
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push({0,k});
        while(!pq.empty()){
            auto top = pq.top();
            int curNode = top.second;
            int curCost = top.first;
            vis[curNode]=true;
            // cout<<"curNode: " << curNode<<"  curCost:" <<curCost<<endl;
            pq.pop();
            for(int i=0; i<adj[curNode].size(); i++){
                int newCost = mat[k][curNode] + mat[curNode][adj[curNode][i]];
                int oldCost = mat[k][adj[curNode][i]];
                // cout<<"newCost: "<<newCost<<"   oldCost: "<<oldCost<<"    childNode:"<<adj[curNode][i]<<endl;
                if(newCost <= oldCost && !vis[adj[curNode][i]]){
                    mat[k][adj[curNode][i]] = newCost;
                    pq.push({newCost, adj[curNode][i]});
                }
            }
            cout<<endl;
        }
        int ans=0;
        for(int i=0;i<=n;i++) mat[i][i]=inf;
        // for(int i=0; i<=n; i++){
        //     for(int j=0; j<=n; j++){
        //         cout<<mat[i][j]<< " ";
        //     }
        //     cout<<endl;
        // }
        for(int i=0;i<=n;i++) 
        {
            if(mat[k][i]!=inf)
                ans=max(ans, mat[k][i]);
        }
        bool ifPath = true;
        for(int i=1;i<=n;i++)
        {
            if(i==k) continue;
            if(mat[k][i] == inf) ifPath=false;
        }
        if(ans==0 || !ifPath) return -1;
        return ans;
    }
};
42021