找从1号点出发，使最长的路径最短

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <cstring>

using namespace std;

//找从每个点出发，使最长的路径最短
typedef pair<int, int> PII;
const int N = 1510; // 


int n,m;
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
int st[N]; // 如果为true说明这个点的最短路径已经确定

priority_queue<PII, vector<PII>, greater<PII>> heap;

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
void djk(int start)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[start]=0;
    //st[1]=1;
    heap.push({0,start});
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();

        int ver=t.second;
        int dis=t.first;

        if(st[ver]) continue;
        st[ver]=1;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dis+w[i])
            {
                dist[j]=dis+w[i];
                heap.push({dist[j],j});
            }
        }

    }

}




int main()
{

    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    int res=0x3f3f3f3f+1;


        int ans=0;
        djk(1);
        for(int j=1;j<=n;j++)
        {
            ans=max(ans,dist[j]);
            //cout<<i<<" "<<j<<" "<<dist[j]<<endl;
        }
        res=min(res,ans);

    if(res==0x3f3f3f3f)
    cout<<-1;
    else
    cout<<res;

    return 0;
}

二刷，堆优化djk，掌握

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int,int> pii;
const int N=1100;
int st[N],ne[N],e[N],w[N],h[N],idx,dist[N];
int n,m;
int res;

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int djk(int zd)
{
    priority_queue<pii,vector<pii>,greater<pii>> heap;
    heap.push({0,1});
    dist[1]=0;
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.second;
        int dis=t.first;
        if(st[ver]) continue;
        st[ver]=1;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dis+w[i])
            {
                dist[j]=dis+w[i];
                heap.push({dist[j],j});
            }
        }
    }
    return dist[zd];
}

int main()
{
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    for(int i=2;i<=n;i++)
    {
        res=max(res,djk(i));
    }
    if(res>0x3f3f3f3f/2)
    cout<<-1;
    else
    cout<<res;
    return 0;
}

2023/12/2

没啥难度，堆优化djk
成功ac

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;
const int N = 1510; 
int n,m;
int e[N],ne[N],h[N],w[N],idx;
int st[N],dist[N];
// 目标: 找从1号点出发，最长的最短路径

void add(int a,int b,int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}


int main()
{
    cin>>n>>m;
    memset(h, -1, sizeof(h));
    memset(dist, 0x3f, sizeof(dist));

    priority_queue<PII,vector<PII>, greater<PII>> heap;

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    heap.push({0, 1});
    dist[1] = 0;

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int var = t.second;
        int d = t.first;

        if(st[var]) continue;

        st[var] = 1;

        for(int i=h[var];i!=-1;i=ne[i])
        {
            int j=e[i];

            if(dist[j] > d+w[i])
            {
                dist[j] = d+w[i];
                heap.push({dist[j], j});
            }
        }
    }

    int res=0;

    for(int i=1;i<=n;i++)
    {
        res=max(res, dist[i]);
    }

    if(res>0x3f3f3f/2)
    {
        cout<<-1;
    }
    else
    {
        cout<<res;
    }



    return 0;
}