Soft_cute @ 2023-08-10 18:38:55
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N=1e4+10,M=1e5+10;
int n,m,s,a[N][N];
struct Node{
vector<int> childs;
int dis;
int deep;
int size;
bool f=false;
}g[N];
struct cmp{
bool operator() (const Node &a,const Node &b){
return a.dis>b.dis;
}
};
void add(int x,int y,int z){
g[x].childs.push_back(y);
g[y].childs.push_back(x);
g[x].size=x,g[y].size=y;
a[x][y]=a[y][x]=z;
}
void dijkstra(){
for(int i=1;i<=n;i++) g[i].dis=inf;
priority_queue<Node,vector<Node>,cmp> heap;
heap.push(g[1]);
while(heap.size()){
Node t=heap.top;
heap.pop();
int ver=t.size,distance=t.dis;
if(g[ver].f) continue;
g[ver].f=true;
for(int i=0;i<g[ver].childs.size();i++){
int j=g[ver].childs[i];
if(g[j].dis>distance+a[i][j]){
g[j].dis=distance+a[i][j];
heap.push(g[j]);
}
}
}
if(g[n].dis==inf) return -1;
return g[n].dis;
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int x,y,c;
cin>>x>>y>>c;
add(x,y,c);
}
cout<<dijkstra();
}
我写的不怎么对,不知道优先队列怎么用
by mmr123 @ 2023-08-10 18:42:06
<类型,实现,比较器>
by KAqwq @ 2023-08-10 18:44:37
priority_queue<Node,vector<Node>,greater<Node> >
之后看看有没有别的问题
by Soft_cute @ 2023-08-10 18:46:00
实现是什么?
by pengrongxuan @ 2023-08-21 20:49:42
优先队列公式:
priority_queue<类型> 队列名称;
如:
priority_queue<int> q;
如果有多个数据,需要:
priority_queue<pair<类型1,类型2> > 队列名称;
如:
priority_queue<pair<int,int> > q;//最后的两个右括号需要分开一个空格,不然会被认为是右移>>运算符
优先队列函数:
q.size();//返回q里元素个数
q.empty();//返回q是否为空,空则返回1,否则返回0
q.push(k);//在q的末尾插入k,多个数据需要使用
//q.push(make_pair(a,b));
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素
q.top().first;//返回q的第一个元素的第一项
q.top().second;//返回q的第一个元素的第二项