这道题应该是比较明显的最短路变形了。一开始用了spfa，TLE了。。后来发现dijkstra+堆优化时间复杂度可以降到O(mlogm)，改用这个算法就可以了，对应改下结构体和dijkstra函数。另外注意无向图加两次边，edge数组也要开两倍(我就一直WA在了这个点上QAQ...)
附上AC代码：
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<queue> using namespace std; #define ll long long typedef pair<int,int>pp; #define mkp make_pair #define pb push_back const int INF=0x3f3f3f3f; const int MAXN=100005; const int MAXM=200005; int n,m; struct Edge { int to,next; int idc; }edge[MAXM*2];//注意要乘2！ int head[MAXN],tot; void init() { memset(head,-1,sizeof(head)); tot=0; } void addedge(int u,int v,int w) { edge[tot].to=v;edge[tot].next=head[u];edge[tot].idc=w;head[u]=tot++; } struct qnode { int v,c,w,pre;//顶点,权值号,dis[v],父节点 qnode(int _v=0,int _c=0,int _w=0,int _pre=0): v(_v),c(_c),w(_w),pre(_pre) {} bool operator < (const qnode &r) const { return w>r.w;//注意是大于！ } }; bool vis[MAXN]; int dis[MAXN]; void dijkstra() { memset(vis,false,sizeof(vis)); memset(dis,INF,sizeof(dis)); dis[1]=0; priority_queue<qnode>q; while(!q.empty()) q.pop(); q.push(qnode(1,-1,0,-1)); qnode tmp; while(!q.empty()) { tmp=q.top(); q.pop(); int u=tmp.v; if(u==n) return; if(vis[u]) continue; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v==tmp.pre) continue; int w=edge[i].idc; int cost=0; if(w!=tmp.c) cost++; if(!vis[v]&&dis[v]>dis[u]+cost) { dis[v]=dis[u]+cost; q.push(qnode(v,w,dis[v],u)); } } } } int main() { while(scanf("%d%d",&n,&m)==2) { init(); if(m==0) { printf("-1\n"); continue; } int u,v,w; for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dijkstra(); if(dis[n]==INF) printf("-1\n"); else printf("%d\n",dis[n]); } return 0; }
