题眼:保证答案不超过1e6
如果这个图上只有小路,没有大路,就表示我们的$dist^2<=1e6$
这就说明,我们这张图上连续的小路,没有长度超过$1000$的
然后就可以做标准的拆点dijkstra了
在这里有一个公式要推导一下,设当前到达节点为u, 下一个节点为v, 两个节点之间是小路
且这段路长d, 再设我们已经连续走了k的距离的小路, 这一整段小路是从t号点开始走的
那么就有如下公式
$dist[u] = dist[t] + k^2 => dist[t] = dist[u]-k^2 …(1)$
$dist[v] = dist[t] + (k+d)^2$
$将(1)式中的dist[t]代入$
$dist[v] = dist[u]-k^2+(k+d)^2 => dist[v] = dist[u] + 2kd + d^2$
这样就能从$dist[u]$ 推理出 $dist[v]$ 的值了
然后我们拆点就可以了
注意!! 因为dist[N][1000]的限制 , 但在代码里多处可能数组越界, 所以需要很多剪枝来防止越界
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 2e5+10, K = 1050;
int h[N], e[M], type[M], w[M], ne[M], idx;
int dist[N][K];
bool st[N][K];
typedef pair<int, pair<int,int>> PII;
int n,m;
void add(int t, int a, int b, int c) // 添加一条边a->b,边权为c
{
e[idx] = b, w[idx] = c, type[idx]=t,ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra(){
priority_queue<PII,vector<PII>,greater<PII>> heap;
memset(dist,0x3f,sizeof dist);
dist[1][0]=0;
heap.push({0,{1,0}});
while(heap.size()){
auto t=heap.top();heap.pop();
int ver=t.second.first,con=t.second.second;
if(st[ver][con]) continue;
st[ver][con] = true;
for(int i=h[ver];~i;i=ne[i]){
int j=e[i];
if(type[i]){
int num=dist[ver][con]+w[i]*w[i]+2*con*w[i];
if(con+w[i]<=1010&&num<dist[j][con+w[i]]){
dist[j][con+w[i]]=num;
if(num<=1e6) heap.push({dist[j][con+w[i]],{j,con+w[i]}});
}
}
else{
if(dist[j][0]>dist[ver][con]+w[i]){
dist[j][0]=dist[ver][con]+w[i];
if(dist[j][0]<=1e6) heap.push({dist[j][0],{j,0}});
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- ){
int t,a,b,c;
scanf("%d%d%d%d",&t,&a,&b,&c);
add(t,a,b,c);
add(t,b,a,c);
}
dijkstra();
int res=1e9;
for(int i=0;i<=1010;i++){
res=min(res,dist[n][i]);
}
printf("%d",res);
return 0;
}
牛牛牛!
牛啊老哥