1个多月没有发题解了

光顾着写算法了

题目描述
寒假到了，n 头牛都要去参加一场在编号为 x 的牛的农场举行的派对，农场之间有 m 条有向路，每条路都有一定的长度。
每头牛参加完派对后都必须回家，无论是去参加派对还是回家，每头牛都会选择最短路径，求这 n 头牛的最短路径（一个来回）中最长的一条路径长度。

输入格式
第一行有三个整数，分别表示牛的数量 n，道路数m 和派对农场编号 x。
接下来 m 行，每行三个整数 u,v,w，表示存在一条由 u 通向 v 的长度为 w 的道路。
输出格式
输出一行一个整数表示答案。

输入输出样例
输入 #1
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
输出 #1
10

这题抽象起来很简单，明显的一个图论最短路径

唯一一个与正常的最短路径不一样的就是他求的是一个来回

并且是有向图，也就是说，去和回的最短路径也许不一样

于是大家兴高采烈的用dijkstra去了

超时了？没关系我还有优先队列

没错就是这么简单

AC了

# include 
# include 
# include 
# include 
# include 
using namespace std;
# define int long long
int n,m,x,m2;
struct node{int to;int next;int w;
}e[100005];
struct node2{int idx,sum;
};
int adj[1005];
int f[1005];
int flag=0,v[1005],maxn=-1;
struct cmp{bool operator()(node2 &a,node2 &b){return a.sum>b.sum;}
};
priority_queue ,cmp> q;
void add(int u,int v,int w){m2++;e[m2].to=v;e[m2].next=adj[u];e[m2].w=w;adj[u]=m2;
}
bool relax(int u,int v,int w){if (f[v]>f[u]+w){f[v]=f[u]+w;return true;}return false;
}
void dijkstra(int s,int t){memset(f,0x3f,sizeof(f));memset(v,0,sizeof(v));f[s]=0;q.push(node2 {s,f[s]});while(!q.empty()){node2 cur=q.top();q.pop();if (v[cur.idx]){continue;}v[cur.idx]=1;for (int k=adj[cur.idx];k;k=e[k].next){int l=e[k].to;if (!v[l]){if (relax(cur.idx,l,e[k].w)){q.push(node2{l,f[l]});}}} }
}
signed main(){scanf("%lld%lld%lld",&n,&m,&x);for (int i=1;i<=m;i++){int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);add(u,v,w);}for (int i=1;i<=n;i++){if(i==x){continue;}dijkstra(i,x);int now_=f[x];dijkstra(x,i);now_+=f[i];if(now_>maxn){maxn=now_;}}printf("%lld",maxn);return 0;
}

如果你觉得有些水

没关系我也这么认为（doge）

有什么问题随时评论区问