科技成果展示网站建设方案,建设工程合同司法解释,富阳做网站方式,合肥知名建站公司题目#xff1a;
样例#xff1a; 输入 4 5 0 2
0 1 2 1
0 2 5 1
0 3 1 2
1 2 1 6
3 2 2 3 输出 3 5 思路#xff1a; 根据题目意思#xff0c;其实还是Dijkstra 的题目#xff0c;不同的是#xff0c;多了一个最少花费边权的这个点#xff0c;多添加一个spend数组
样例
输入 4 5 0 2
0 1 2 1
0 2 5 1
0 3 1 2
1 2 1 6
3 2 2 3 输出 3 5 思路 根据题目意思其实还是Dijkstra 的题目不同的是多了一个最少花费边权的这个点多添加一个spend数组结合dist数组即可同样用堆优化方式更方便些。
代码详解如下
#include iostream
#include cstring
#include algorithm
#include queue
#include unordered_map
#define endl \n
#define int long long
#define YES puts(YES)
#define NO puts(NO)
#define umap unordered_map
#define INF 0x3f3f3f3f3f3f3f3f3f3f
#define All(x) (x).begin(),(x).end()
#pragma GCC optimize(3,Ofast,inline)
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N 2e6 10;int n,k,start,last;int dist[N]; // 最短距离数组
int spend[N]; // 最少花费边权数组
bool st[N]; // 标记是否走动过// 定义存储 点距离边权 结构体
struct Edge
{int b; // 关系点int dis; // 距离int m; // 边权花费// 构造函数inline Edge(int _b,int _dis,int _m){b _b;dis _dis;m _m;}// 重载比较符号方便堆排序inline bool operator(const Edgew)const{// 优先选择 最短距离其次距离相等的时候选择最少边权的花费if(dis ! w.dis) return dis w.dis;else return m w.m;}
};// 建立链表e 存储的是关系点w 存储的是距离m 存储的是边权
int h[N],w[N],m[N],ne[N],e[N],idx;
inline void Add(int a,int b,int c,int d)
{e[idx] b,w[idx] c,m[idx] d,ne[idx] h[a],h[a] idx;
}inline void Dijkstra()
{// 初始化最短距离数组和最少花费边权数组memset(dist,INF,sizeof dist);memset(spend,INF,sizeof spend);dist[start] 0;spend[start] 0;priority_queueEdgeq;// 存储起点q.push(Edge(start,0,0));while(q.size()){// 获取当前存储的边权距离关系Edge now q.top();q.pop();int b now.b; // 获取相应关系点int dis now.dis; // 获取相应关系距离int spe now.m; // 获取相应关系花费边权// 如果当前的 b 点走动过进入下一个关系点的判断if(st[b]) continue;st[b] true; // 标记当前点// 遍历连接的链表关系for(int i h[b];i ! -1;i ne[i]){int j e[i]; // 获取 与 b 点连接的 相应的关系点// 更新关系点的最短距离if(dist[j] dis w[i]){dist[j] dis w[i]; // 由于一定会更新最短距离所以花费也一定会更新spend[j] spe m[i];}else // 否则如果最短距离相同我们选择更新最少花费边权的if(dist[j] dis w[i] spend[j] spe m[i]) spend[j] spe m[i];// 存储该关系点进行下一次走动q.push(Edge(j,dist[j],spend[j]));}}
}inline void solve()
{cin n k start last;while(k--){int a,b,c,d;cin a b c d;// 由于是无向图所以添加两个点互相的链表Add(a,b,c,d);Add(b,a,c,d);}Dijkstra();// 输出答案cout dist[last] spend[last] endl;
}
signed main()
{// 初始化链表memset(h,-1,sizeof h);
// freopen(a.txt, r, stdin);___G;int _t 1;
// cin _t;while (_t--){solve();}return 0;
}
最后提交
