感谢光神送来rating38000分的思路
题目描述
会和神奈子一起改变地形，开凿地下洞穴等。虽说是一起，不过看起来改变土地是诹访子的工作。与其说她是直接将大地整平，不如说这是她麾下的崇神的功劳。——「求闻口授」
山路交错相同，令人烦躁。
于是诹访子想要将山路重新规划，具体的说，山路可以看成 n 个点，m 条边的无向图。她会在这幅图上的基础之上添加一些边，具体的说，她会给每个点设一个权值ai ，然后将点两两之间连边，假如连了一条边为(i,j) ，那么这条边的长度为|ai + k × aj| ，其中 k=1 或 -1。
几千年过去之后，已经没什么人再记得曾经有诹访子这样一位神，然而山路却完整地保留到了今天。
那么你作为一个普通人，现在想要从 1 号点走到 n 号点去，你想知道最短的路径长度是多少？
输入
第一行三个数：n,m,k 。
接下来 m 行：每行三个数ui,vi,wi ，描述一条边连接 ui,vi 长度为 wi。
接下来一行： n个整数，第 i 个整数表示ai。
输出
一行一个整数代表答案。
样例输入 Copy
3 1 -1
1 2 3
1 7 8
样例输出 Copy
4
题目思路
k有两种取值，一种是-1,一种是1,影响的是两点间新建边的权值
1。 k=-1时候,|ai + k × aj|肯定时临项最小，然后建边
这样建出一颗最小生成树
这颗最小生成树，是满足任意两点间的最短距离都在这课树上的
2。 k=1的时候，如果我们在建最小生成树是不满足任意两点最短距离都在树上的，只能够满足任意亮点相互到达使总的代价最小
这时候建立一个超级原点，就能满足边权为a[i]+a[j]因为超级原点的连接的两条边权一条为a[i].w一条为a[j].w
最后跑一个最短路就行了
Code
int n,m,k,head[maxn],cnt,dist[maxn];
vector<PII>zan[maxn];
map<PII,int>mp;
struct node {
int id,val;
} a[maxn];
struct Node {
int u,v,w,next;
} e[maxn];
bool cmp(node x,node y) {
return x.val<y.val;
}
void add(int u,int v,int w) {
e[cnt].u=u,e[cnt].v=v;
e[cnt].w=w,e[cnt].next =head[u];
head[u]= cnt++;
}
void D() {
dist[1] = 0;
dist[0] = inf;
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push({0,1});
while(q.size()) {
PII fr=q.top();
q.pop();
int dis = fr.first;
int dian =fr.second;
for(int i=head[dian]; ~i; i=e[i].next) {
int v=e[i].v;
if(dist[v]>dis+e[i].w) {
dist[v] = dis +e[i].w;
q.push({dist[v],v});
}
}
}
out(dist[n]);
}
int main() {
n=read(),m=read(),k=read();
mst(head,-1);
for(int i=1 ; i<=m ; i++) {
int u,v,w;
u=read(),v=read(),w=read();
zan[u].push_back({v,w});
add(u,v,w);
add(v,u,w);
mp[{u,v}]=1;
}
for(int i=1 ; i<=n ; i++) {
a[i].val=read();
a[i].id=i;
dist[i] = inf;
}
sort(a+1,a+1+n,cmp);
if(k==-1) {
for(int i=1 ; i<n ; i++) {
int u = a[i].id ;
int v = a[i+1].id;
if(mp[{u,v}]) continue;
add(a[i].id,a[i+1].id,abs(a[i].val+k*a[i+1].val));
add(a[i+1].id,a[i].id,abs(a[i].val+k*a[i+1].val));
mp[{u,v}]=1;
}
} else if(k==1) {
for(int i=1 ; i<=n ; i++) {
add(a[i].id,0,a[i].val);
add(0,a[i].id,a[i].val);
}
}
D();
