队列优化
题目描述
这些路线包括起始点和终点一共有 T 个城镇,为了方便标号为 1 到 T。
除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。
每条道路有一个通过费用(包括油费,过路费等等)。
给定一个地图,包含 C 条直接连接 2 个城镇的道路。
每条道路由道路的起点 Rs,终点 Re 和花费 Ci 组成。
求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。
输入样例
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
输出样例
7
C++ 代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define N 100000
using namespace std;
struct node {
int zd,val;
node(int xx,int yy):zd(xx),val(yy) {}
};
vector<node>adj[N];
queue<int>q;
int n,m,te,ts;
int book[N];
int f[N];
int main() {
memset(book,0,sizeof(book));
memset(f,0x3f,sizeof(f));
cin>>n>>m>>te>>ts;
for (int i=1; i<=m; i++) {
int x,y,z;
cin>>x>>y>>z;
adj[x].push_back(node(y,z));
adj[y].push_back(node(x,z));
}
f[te]=0;
book[te]=1;
q.push(te);
while(!q.empty()) {
int k=q.front();
book[k]=0;
q.pop();
for (int i=0; i<adj[k].size(); i++) {
int xx=adj[k][i].zd,yy=adj[k][i].val;
if(f[xx]>f[k]+yy) {
f[xx]=f[k]+yy;
if(book[xx]==0) {
book[xx]=1;
q.push(xx);
}
}
}
}
cout<<f[ts]<<endl;
return 0;
}
结语
这种题较基础,用于手熟,但也不可忽略,万一赛场上模板忘了怎么办ヾ(๑╹◡╹)ノ"