[LeetCode每日一题]743. 网络延迟时间

ygxdsh

非常经典的最短路问题，用djks轻松解决

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        int djks[110],a[110][110]={0};
        bool b[110]={0};
        memset(djks,0x3f,sizeof(djks));
        memset(a,0x3f,sizeof(a));
        for(auto x:times)
        {
            a[x[0]][x[1]]=min(a[x[0]][x[1]],x[2]);
        }
        djks[k]=0;
        for(int i=1;i<=n;i++)
        {
            int minn=0x3f3f3f3f,k=-1;
            for(int j=1;j<=n;j++)
            {
                if(!b[j]&&djks[j]<minn)
                {
                    minn=djks[j];
                    k=j;
                }
            }
            if(k==-1) break;
            b[k]=1;
            for(int j=1;j<=n;j++)
            {
                if(!b[j])
                djks[j]=min(djks[j],djks[k]+a[k][j]);
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            ans=max(ans,djks[i]);
        }
        return ans==0x3f3f3f3f?-1:ans;
    }
};

Mr-Hate

迪杰斯特拉启动！🥵

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        const int inf=INT_MAX/2;
        vector<vector<int>> g(n+1,vector<int>(n+1,inf));vector<bool>vis(n+1,false);vector<int> dist(n+1,inf);
        for(auto& t:times){
            int x=t[0],y=t[1];
            g[x][y]=t[2];
        }
        dist[k]=0;
        for(int i=1;i<n;i++){
            int mmin=0;
            for(int j=1;j<=n;j++){
                if(!vis[j]&&(mmin<1||dist[j]<dist[mmin]))
                mmin=j;
            }
            vis[mmin]=true;
            for(int j=1;j<=n;j++){
                dist[j]=min(dist[j],dist[mmin]+g[mmin][j]);
            }
        }
        int mmax=*max_element(dist.begin()+1, dist.end());
        return mmax==inf?-1:mmax;
    }
};