链式前向星——有向图的权重（板子）
2026-02-04 21:17:01
发布于：浙江
3阅读
0回复
0点赞
模板！供学习参考，会更！（我自己都不信）
（￣︶￣）↗ 出发！
#include<bits/stdc++.h>
using namespace std;
const int mn=1e5+10;
struct node{
int to;//终点
int next;//下一位置
int w;//权重
}e[mn];//边结构体数组
int head[mn];//链表数组，顶点链表初始位置
int cnt;//已经加入的边数
void add(int u,int v,int w){//插入一条新的边
//表示新边的节点
e[++cnt].to=v;
e[cnt].w=w;
//新节点指向u的链表的链头
e[cnt].next=head[u];
//新的节点作为新的链头
head[u]=cnt;
}
int main(){
int n,m;
cin>>n>>m;
while(m--){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);//添加一条边
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=head[i];j;j=e[j].next){
//head[i]:顶点i的第一条边在数组上的位置
//j:正在处理的边
//e[j].next:下一题从i开始出发的边
ans+=e[j].w;
}//把从顶点i出发的所有边都走一遍
}
cout<<ans;
return 0;
}
这里空空如也
有帮助，赞一个