题目大意:
给定无向图的 n m 为点数和边数
接下来 m 行给定 u v id 表示点 u 到点 v 间有一条编号为 id 的边
当由一条边走到另一条边 而两条边的编号不同时 费用 + 1
优先队列跑 dijkstra 最短路 按费用排序
- #include <bits/stdc++.h>
- using namespace std;
- #define INF 0x3f3f3f3f
- #define LL long long
- #define mem(i,j) memset(i,j,sizeof(i))
- #define P pair<int,int>
- #define mp make_pair
- #define fir first
- #define sec second
- #define pb push_back
- const int N=1e5+5;
- int n,m;
- vector<P>G[N];
- struct NODE {
- int u,d,id,fa;
- bool operator <(const NODE& p)const {
- return d>p.d;
- }
- };
- int dis[N];
- void dijkstra() {
- priority_queue<NODE>q;
- while(!q.empty()) q.pop();
- q.push({1,0,0,-1}); dis[1]=0;
- while(!q.empty()) {
- NODE e=q.top(); q.pop();
- int u=e.u;
- if(u==n) break;
- for(int i=0;i<G[u].size();i++) {
- P t=G[u][i];
- int v=t.fir;
- if(u==v) continue;
- if(dis[v]>dis[u]+(t.sec!=e.id)) {
- dis[v]=dis[u]+(t.sec!=e.id);
- q.push({v,dis[v],t.sec,u});
- }
- }
- }
- }
- void init() {
- mem(dis,INF);
- for(int i=1;i<=n;i++) G[i].clear();
- }
- int main()
- {
- while(~scanf("%d%d",&n,&m)) {
- init();
- while(m--) {
- int u,v,id;
- scanf("%d%d%d",&u,&v,&id);
- G[u].pb(mp(v,id));
- G[v].pb(mp(u,id));
- }
- dijkstra();
- if(dis[n]==INF) printf("-1\n");
- else printf("%d\n",dis[n]);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2949125.html