当前位置: 首页 > >

csu1808(优先级队列+Dijkstra)

发布时间:

解题思路 以边为单位计算 优先级队列存储与起点最短的边的长度


#include "set"
#include "queue"
#include "cmath"
#include "vector"
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "iostream"
#include "algorithm"
#include "iostream"
using namespace std;
#include maxn 100002
#include len le18;
struct Edge //储存边的信息
{
int a,b;
long long c,t;
}edge[maxn];

struct node // 优先级队列的构造
{
int i;
long long val;
};

bool operator<(node a,node b) // 优先级队列的构造 2
{
return a.val>b.val; //注意 "<"为从大到小排列,">"为从小到大排列
};
vectormrpe[maxn];
int vis[maxn];
long long dis[maxn];

int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int a,b;
long long c,t;
priority_queue q;
for(int i=0;i<=n;i++)
mrpe[i].clear();
memset(vis,0,sizeof(vis));
for(int i=0;i dis[i]=len;// 初始化
for(int i=0;i {
scanf("%d%d%lld%lld",&edge[i].a,&edge[i].b,&edge[i].c,&edge[i].t);
if(min(edge[i].a,edge[i].b)==1)//判断是否为起点
{
dis[i]=edge[i].t;
q.push(node{i,edge[i].t});
}
mrpe[edge[i].a].push_back(i);// mp存入边的信息
mrpe[edge[i].b].push_back(i);
}
while(!q.empty()) //队列的使用
{
node na=q.top();
int x=na.i; // 为最短的边
//printf("%d
",x);
q.pop();
if(vis[x])
continue;
vis[x]=1;
int a=edge[x].a;
int b=edge[x].b;
for(int i=0;i {
int y=mrpe[a][i];
long long val=edge[y].c-edge[x].c;
if(val<0)
val=-val;
if(dis[y]>dis[x]+val+edge[y].t){
dis[y]=dis[x]+val+edge[y].t;
q.push(node{y,dis[y]});
}
}
for(int i=0;i {
int y=mrpe[b][i];
long long val=edge[y].c-edge[x].c;
if(val<0)
val=-val;
if(dis[y]>dis[x]+val+edge[y].t){
dis[y]=dis[x]+val+edge[y].t;
q.push(node{y,dis[y]});
}
}
}
long long mis=1e18;
for(int i=0;i mis=min(mis,dis[mrpe[n][i]]);
printf("%lld
",mis);
}
return 0;
}

// 多动手总会有收获加油



友情链接: