传送门 https://www.luogu.org/problemnew/show/P2299
dijkstra 的模板题
- #include<iostream>
- #include<vector>
- #include<queue>
- using namespace std;
- int n,m;
- const int inf=99999999;
- vector<pair<int,int>>g[2505];
- int book[2505];
- int dis[2505];
- priority_queue<pair<int,int>>q;//pair 第一位存最短路, 第二位存顶点编号, 每次取小的优先队列
- void dijkstra()
- {
- for(int i=1;i<=n;i++)dis[i]=inf;
- dis[1]=0;
- q.push(make_pair(dis[1],1));
- while(q.size())
- {
- int x=q.top().second;
- q.pop();
- if(book[x]==1)continue;
- book[x]=1;
- for(int i=0;i<g[x].size();i++)
- {
- int y=g[x][i].first;
- if(dis[y]>dis[x]+g[x][i].second)
- {
- dis[y]=dis[x]+g[x][i].second;
- q.push(make_pair(-dis[y],y));
- }
- }
- }
- }
- void solve()
- {
- cin>>n>>m;
- for(int i=1;i<=m;i++)
- {
- int a,b,c;
- cin>>a>>b>>c;
- g[a].push_back(make_pair(b,c));// 第一位使顶点编号, 第二位是权值
- g[b].push_back(make_pair(a,c));
- }
- dijkstra();
- cout<<dis[n]<<endl;
- }
- int main()
- {
- solve();
- }
来源: http://www.bubuko.com/infodetail-2874310.html