#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxv=520;
const int INF=1000000000;
//利用pre数组先求出每个点的点权或边权之和的模板。可直接照搬
//1、使用Dijkstra算法记录所有最短路径
vector<int> pre[maxv];
void Dijkstra(int s)
{
fill(d,d+maxv,INF);
d[s]=0;
for(int i=0;i<n;++i)
{
int u=-1;min=INF;
for(int j=0;j<n;++j)
{
if(vis[j]==false&&d[j]<min)
{
u=j;
min=d[j];
}
}
if(u==-1)
return ;
vis[u]=true;
for(int v=0;v<n;++v)
{
if(vis[v]==false&&G[u][v]!=INF)
{
if(d[u]+G[u][v]<d[v])
{
d[v]=d[u]+G[u][v];//优化d[v]
pre[v].clear(); //清空pre
pre[v].push_back(u); //记录v的前驱u
}
else if(d[u]+G[u][v]==d[v])
pre[v].push_back(u); //记录v的前驱u
}
}
}
}
//2、遍历所有最短路径，找出一条使第二标尺最优的路径。
//DFS 递归函数
//1.1 作为记录第二尺度最优值的全局变量optvalue
//1.2 记录最优路径的数组path（vector实现）
//1.3 记录遍历到叶子结点时的路径，temppath（vector）
int optvalue; //第二尺度最优值
vector <int> pre[maxv];
vector<int> path,temppath;
void DFS(int v) //v为当前访问结点
{
if(v==st) //递归边界，如果到达了叶子结点st，即路径的起点
{
temppath.push_back(v);//将起点st加入临时路径temppath最后面
int value; //记录临时路径temppath的第二标尺的值
计算路径temppath上的value值；
if(value优于optvalue)
{
optvalue=value;
path=temppath;
}
temppath.pop_back(); //将刚加入的结点删除
return;
}
//递归式
temppath.push_back(v); //将当前访问结点加入临时路径temppath最后面
for(int i=0;i<pre[v].size();++i)
DFS(pre[v][i]); //结点v的前驱结点pre[v][i],递归
temppath.pop_back(); //遍历完所有前驱结点，将当前结点v删除
}
//3、计算temppath上边权和点权之和
//边权之和
int value=0;
//由于递归的原因，temppath中的结点是逆序的。固应倒着访问结点，循环条件为i>0
for(int i=temppath.size()-1;i>0;--i)
{
//当前结点为id，下一个结点为idnext；
int id=temppath[i],idnext=temppath[i-1];
value+=v[id][idnext]; //value值累加边id->idnext 的边权
}
// 点权之和计算方法
int value =0;
for(int i=temppath.size()-1;i>=0;--i) //倒着访问结点，循环条件为i>=0
{
//当前结点为id
int id=temppath[i];
value+=w[id]; //value值累加结点id 的点权
}
