文章
72
粉丝
142
获赞
5
访问
57.6k
#include<iostream>
#include<string>
#include<climits>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 1000 + 5;
struct edge {
int to;
int length;
int price;
};
struct node {
int number;
int distance;
int price;
};
bool operator<(node l,node r) {
return l.distance > r.distance;
}
vector<edge> graph[maxn];
int dis[maxn];
int qian[maxn];
int visited[maxn];
void Dij(int s,int t,int n) {
priority_queue<node> myqueue;
for (int i = 1; i <=n;i++) {
visited[i] = 0;
}
dis[s]=0;
qian[s] = 0;
myqueue.push(node{s,dis[s],qian[s]});
while (!myqueue.empty()) {
...
登录后发布评论
这个同学的算法实现跟你的是一样的,Dijstra+优先队列实现,可以参考一下
https://noobdream.com/DreamJudge/Issue/code/144913/
这个题的n的上限是1000,可以用O(n^2)的复杂度算法
建议先用朴素的Dijstra算法来实现,通过了之后再考虑用现在这个堆优化的O(nlogn)算法实现