回复 @Hallmeow :
我也是膜了半天题解 orz orz

蒟蒻表示膜了半天题解也没膜懂
@yymxw dalao 2A+rank1
扑通扑通跪下来QAQ

8……848？？！！

谁能告诉我第二个点的逻辑是什么？

这tm卡常...

被坑了

这数据太水了,n^2暴力直接过

上大学了居然还要再学一遍treap
这里的数据似乎有些小，我两个哨兵开了±0x7fffffff(8个f)也过了
我的题解：http://wmdcstdio.com/2017/10/27/poj-1442neerc-1996black-box/

所需知识
1.拓扑
2.没了
注意传导要是活跃状态

回复 @GaoErFu : 可以试一试记忆化搜索。

floyd在第7个点三秒半，看来70以上还是djs

。。。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
inline int read(){
int num=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){num=(num<<1)+(num<<3)+(c^48); c=getchar();}
return num*f;
}
#define maxn 500
vector<int>a[maxn],b[maxn];
queue<int>s;
int n,m,dis[maxn],diss[maxn],dk[maxn],maxx=127,tt;
bool jud[maxn];
inline int in(){
n=read(); m=read();
for(int i=1;i<=m;i++){
int u,v,c;
u=read(); v=read(); c=read();
a[u].push_back(v);
a[v].push_back(u);
b[u].push_back(c);
b[v].push_back(c);
}
}
inline int spfa(int x,int y){
memset(jud,0,sizeof(jud));
memset(dis,10,sizeof(dis));
dis[x]=0;
s.push(x);
while(!s.empty()){
int city=s.front();
s.pop();
int num=a[city].size();
for(int i=0;i<num;i++){
int next=a[city][i];
int next_c=b[city][i];
if(dis[next]>dis[city]+next_c){
dis[next]=dis[city]+next_c;
if(!jud[next]){
s.push(next);
jud[next]=1;
}
}
}
}
memset(jud,0,sizeof(jud));
memset(diss,10,sizeof(diss));
diss[y]=0;
s.push(y);
while(!s.empty()){
int city=s.front();
s.pop();
int num=a[city].size();
for(int i=0;i<num;i++){
int next=a[city][i];
int next_c=b[city][i];
if(diss[next]>diss[city]+next_c){
diss[next]=diss[city]+next_c;
if(!jud[next]){
s.push(next);
jud[next]=1;
}
}
}
}
for(int i=0;i<n;i++) dk[i]=min(dis[i],diss[i]);
int ha=0;
for(int i=0;i<n;i++) ha=max(ha,dk[i]);
return ha;
}
int x,y;
inline int work(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i!=j){
int ans=spfa(i,j);
if(maxx>ans){
maxx=ans;
x=i,y=j;
}
}
}
}
}
inline int out(){
cout<<min(x,y)<<" "<<max(x,y);
}
int main(){
freopen("djsb.in","r",stdin);
freopen("djsb.out","w",stdout);
in();
work();
out();
}

zz地打错了文件名
zz地打错了for循环边界
zz地打错了数组名
我。。。

在原代码上改了又改改的丑的看不了了qwq

背包动规第一题留念/滑稽

long long

坑爹读入

唉 没注意楼上各位仁兄提醒啊~~~

细节的处理是食人的妖魔