image.png
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
算法思想：
从已占领的节点往邻接节点扩张，选择所有邻接节点中value+dis[i]权值之和最低的加入已占领集合{}，直到无法再添加新节点时遍历结束。
PS: 一个个局部最优最后竟然成为了全局最优。
#include <bits/stdc++.h>
using namespace std;
typedef struct{
int num;
int value;
bool isfull;
}Node;
bool sign[1000]={false}; // 是否已被占领
int dis[1000]={0}; // 距离矩阵
vector<int>conquer;
int points=0; // 点的个数
// 如果是无向图（可双向行驶），所以需要两边填充，a到b和b到a
// 但是这个例子是单向有向图，所以不需要
int choose(vector<vector<Node>>v,queue<int>q){
int i,j,choosed=-1; // 最佳节点初始为一个不存在的-1，方便查找失败的判断
int min_value=1000000000; // 选一个最大值作为初始最小值，这样才好比较式替换
while(!q.empty()){
int head=q.front();
q.pop();
if(v[head][0].isfull==false){
bool isfull=true; // 如果都已经占领，下次就不用再遍历了
for(i=1;i<v[head].size();i++){
// 对所有已占领节点可以直达(相邻)的节点（sign==false）遍历，看看能否找到最短的直连路径然后将其占领（return choosed;）
if(sign[v[head][i].num]==false){
isfull=false;
// 有活节点标记，isfull标记用
// value+最近已占领节点的dis[head]如果更小则替换最佳节点和min_value
if(dis[head]+v[head][i].value<min_value){
choosed=v[head][i].num;
min_value=dis[head]+v[head][i].value;
}
}
}
if(isfull==true){
v[head][0].isfull=true; // 整个图一个空的都没有，满了isfull=true
}
}
}
if(choosed==-1){
return -1; // 很遗憾，并不是所有节点都可以占领
}
sign[choosed]=true; // 很幸运，你占领了一个新节点，在sign上做个标记然后吧distance写入dis数组
dis[choosed]=min_value;
return choosed;
}
void show(){
int i,j;
for(i=1;i<points+1;i++){
cout<<"sign:"<<sign[i]<<" ";
}
cout<<endl;
for(i=1;i<points+1;i++){
cout<<"dis:"<<dis[i]<<" ";
}
cout<<endl;
}
void DFS(vector<vector<Node>>v,int start){
queue<int>q;
q.push(start);
int i,j;
int choosed=0; // 选中哪个节点作为天选之子
while(q.size()!=points){
choosed=choose(v,q);
cout<<"\nchoosed:"<<choosed<<endl;
cout<<"value:"<<dis[choosed]<<endl;
if(choosed!=-1){
q.push(choosed);
// 把天选之子放入队列，以后遍历需要用
}
else{
// 为-1说明有节点不可达~，看最后输出的dis是否为0即可判断
break;
}
}
}
int main(){
vector<vector<Node>>v; // 第一行废弃，第二行开始第一列用于标记是否后续已满，只有后面用于记录value
int edges,i,j;
scanf("%d %d",&points,&edges);
//
for(i=0;i<points+1;i++){
vector<Node>vv;
v.push_back(vv);
Node node;
node.num=0;
node.value=0;
node.isfull=false;
v[i].push_back(node);
}
int a,b,value;
for(j=0;j<edges;j++){
scanf("%d %d %d",&a,&b,&value);
Node node;
node.num=b;
node.value=value;
v[a].push_back(node);
}
int start=1;
DFS(v,start);
}
堆优化怎么办？
用priority_queue替换queue，然后对node.dis排序
加了第二标尺的话怎么办？
1.出法1：
每个边加上一个边权（点权），求在有多个相同距离路径时权值最大时的最短路径。
2.出法2：
从A->B存在相同权值的路径的话有几个？打印一下看看。
image.png
前者使用邻接表即可，权值标记在节点上。后者需要开一个数组a[][]/dict缓存边的权值。
