请区分题目背景和题目描述
by 小粉兔 @ 2019-12-22 12:37:31
我不认为你这题能过吧，如果有心请出公开赛，一般不接受个人原创题
by 小粉兔 @ 2019-12-22 12:38:29
算法是分层图？
by Ephemeroptera @ 2019-12-22 12:47:54
这题在别的OJ上有，我做过几遍了
by PrincessQi @ 2019-12-22 13:00:57
分层图咋做啊||@[Dr冯](/user/104662)
by JK_LOVER @ 2019-12-22 13:07:08
@[JK_LOVER](/user/227824) 自己百度（你出了这个题不知道分层图咋做？而且分层图是最简单的紫题算法，你还定了个黑题
by PrincessQi @ 2019-12-22 13:11:52
dalao ,我看了看，这道题用分层图的话，好像是不正确的啊，或者说我太弱了，dalao求代码||@[Dr冯](/user/104662)
by JK_LOVER @ 2019-12-22 13:22:34
```
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 1000000 + 10;
const ll inf = (ll)1e15;
struct edge { int to,nex; ll w; } eg[10000010];
int n,m,k,fir[maxn],egcnt;
bool vis[maxn];
ll dis[maxn];
inline void addedge(int u,int v,ll w) { eg[++egcnt] = { v,fir[u],w }; fir[u] = egcnt; }
priority_queue<pii,vector<pii>,greater<pii> > q;
inline void dijkstra(int s) {
for (int i = 1;i <= n*(k+1);i++) dis[i] = inf;
q.push(make_pair(0,s));
dis[s] = 0;
for (int now;q.size();) {
now = q.top().second; q.pop();
if (vis[now]) continue;
vis[now] = true;
for (int i = fir[now];~i;i = eg[i].nex)
if (dis[eg[i].to] > dis[now]+eg[i].w) {
dis[eg[i].to] = dis[now]+eg[i].w;
q.push(make_pair(dis[eg[i].to],eg[i].to));
}
}
}
int main() {
memset(fir,-1,sizeof(fir));
int s,t;
scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
for (int i = 1,u,v;i <= m;i++) {
ll w; scanf("%d%d%lld",&u,&v,&w);
for (int j = 0;j <= k;j++) {
addedge(j*n+u,j*n+v,w);
addedge(j*n+v,j*n+u,w);
}
for (int j = 0;j <= k;j++)
for (int t = 1;t <= k-j;t++) {
addedge(j*n+u,(j+t)*n+v,w>>t);
addedge(j*n+v,(j+t)*n+u,w>>t);
}
}
dijkstra(s);
ll ans = inf;
for (int i = 0;i <= k;i++) ans = min(ans,dis[i*n+t]);
if (ans == inf) printf("NO");
else printf("%lld",ans);
return 0;
}
```
by PrincessQi @ 2019-12-22 13:48:49
@[JK_LOVER](/user/227824) 这是这个题的原题的代码，你的这个题如果我没看错题的话就是加一个求最远点对qwq
by PrincessQi @ 2019-12-22 13:50:02
原题我A了，我认为如果要求最远点对的话，最短路算法就做不了啊，它不能保证边的要求啊，真的有点不懂||@[Dr冯](/user/104662)
by JK_LOVER @ 2019-12-22 13:56:06