文章目录
- 题意
- 题解
题意
给 一 张 边 带 权 无 向 图 , 让 你 求 一 棵 边 权 和 最 小 的 生 成 树 , 使 得 点 u 在 树 上 到 每 个 点 的 距 离 等 于 u 在 原 图 中 到 每 个 点 的 最 短 路 . 给 出 这 张 图 和 u , 输 出 最 小 边 权 和 以 及 构 成 这 棵 生 成 树 的 边 集 . 给一张边带权无向图,让你求一棵边权和最小的生成树,使得\newline 点u在树上到每个点的距离等于u在原图中到每个点的最短路.\newline 给出这张图和u,输出最小边权和以及构成这棵生成树的边集. 给一张边带权无向图,让你求一棵边权和最小的生成树,使得点u在树上到每个点的距离等于u在原图中到每个点的最短路.给出这张图和u,输出最小边权和以及构成这棵生成树的边集.
题解
大胆贪心,把每一个点相连的最短路上的边相加.
注意最短路算法中进行的松弛操作.
我们对经过每一个点的最短路上的边标记为 e i d v eid_v eidv.
那么在跑最短路的时候,如果 d i s [ v ] > d i s [ u ] + c o s t dis[v]>dis[u]+cost dis[v]>dis[u]+cost,那么 e i d [ v ] = i . i d eid[v]=i.id eid[v]=i.id,即这条边的编号.
如果 d i s [ v ] = d i s [ u ] + c o s t dis[v]=dis[u]+cost dis[v]=dis[u]+cost,我们就贪心选较短的边.
这样下去除了起始点 u u u的所有点 v v v的 e i d eid eid组成的集合即为答案.
#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rel register ll
#define rec register char
#define gc getchar
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?-1:*p1++)
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
char buf[1<<23],*p1=buf,*p2=buf;
inline int read(){int x=0,f=1;char c=gc();for (;!isdigit(c);c=gc()) f^=c=='-';for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');return f?x:-x;}
template <typename mitsuha>
inline bool read(mitsuha &x){x=0;int f=1;char c=gc();for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';if (!~c) return 0;for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');return x=f?x:-x,1;}
template <typename mitsuha>
inline int write(mitsuha x){if (!x) return 0&pc(48);if (x<0) pc('-'),x=-x;int bit[20],i,p=0;for (;x;x/=10) bit[++p]=x%10;for (i=p;i;--i) pc(bit[i]+48);return 0;}
inline char fuhao(){char c=gc();for (;isspace(c);c=gc());return c;}
}using namespace chtholly;
using namespace std;
const int yuzu=3e5,inf=0x3f3f3f3f;
typedef int fuko[yuzu|10];
typedef ll rize[yuzu|10];
struct edge{int to,cost,id;}e[yuzu|10];
vector<edge> lj[yuzu|10];vector<int> ans;
namespace {
rize dis; fuko eid,vis;
void spfa(int s) {memset(dis,0x3f,sizeof dis);queue<int> q;dis[s]=0,q.push(s);for (;!q.empty();) {int u=q.front(); q.pop();vis[u]=0;for (edge i:lj[u]) {int v=i.to; ll c=i.cost;if (dis[u]+c==dis[v]&&e[eid[v]].cost>c){eid[v]=i.id;if (!vis[v]) q.push(v),vis[v]=1;}if (dis[v]>dis[u]+c) {dis[v]=dis[u]+c;eid[v]=i.id;if (!vis[v]) q.push(v),vis[v]=1;}}}}
}int main() {
int i,n,m,u,v,c;
read(n),read(m);
for (i=1;i<=m;++i) {read(u),read(v),read(c);lj[u].push_back(edge{v,c,i});lj[v].push_back(edge{u,c,i});e[i]=edge{v,c,i};}
e->cost=inf;
spfa(read());
ll llx=0;
for (i=1;i<=n;++i) if (eid[i]) ans.push_back(eid[i]),llx+=e[eid[i]].cost;
cout<<llx<<endl;
for (auto p:ans) write(p),p32;
}
谢谢大家.
