题目链接：点击打开链接
题目大意：给一个有向图，求0点到n+1点的最短路径上直接与0点连接的点，如果有多条最短路就输出编号最小的那个。
解题思路：思路就是反向建图，求出终点到起点的最短路径，然后从小到大枚举所有与0点连接的点n，只要 dis[v]+map[v][0]==dis[0] 成立就退出，注意起点直接与终点相连的情况。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1010; int n,m; int vis[maxn], mp[maxn][maxn], dis[maxn]; void init() { mem(vis,0); for(int i=0;i<=n+1;i++) for(int j=0;j<=n+1;j++) mp[i][j]=INF; } void dijkstra(int s) { for(int i=0;i<=n+1;i++) dis[i]=mp[s][i]; dis[s]=0; vis[s]=1; for(int i=0;i<=n+1;i++) { int v=-1, min=INF; for(int j=0;j<=n+1;j++) { if(!vis[j] && dis[j]<min) { min=dis[j]; v=j; } } if(v==-1) return; vis[v]=1; for(int j=0;j<=n+1;j++) { if(!vis[j] && mp[v][j]<INF) { if(dis[j]>dis[v]+mp[v][j]) dis[j]=dis[v]+mp[v][j]; } } } } int main() { int T; scanf("%d",&T); while(T-- && ~scanf("%d%d",&n,&m)) { init(); int u, v, w, near[maxn], k=0; for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); mp[v][u]=w; if(u==0) near[k++]=v; } dijkstra(n+1); if(dis[0]==INF) { puts("-1"); continue; } sort(near,near+k); int rs=-2; for(int i=0;i<k;i++) { v=near[i]; if(dis[0]==dis[v]+mp[v][0]) { if(v==n+1) { rs=0; break; } rs=v; break; } } printf("%d\n",rs); } return 0; }
