admin 管理员组

文章数量: 1087818

山路 (ghat)

感谢光神送来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();

本文标签： 山路 (ghat)

版权声明：本文标题：山路 (ghat) 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1694410020a251731.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。