首页 > 代码库 > sdut3562-求字典序最小的最短路 按顶点排序后spfa的反例
sdut3562-求字典序最小的最短路 按顶点排序后spfa的反例
首先我们可以这么搞...倒序建图，算出源点s附近的点距离终点的距离，然后判断一下，终点是否能跑到源点
能跑到的话呢，我们就判断s周围的点是否在最短路上，然后我们选编号最小的点就好了
代码
#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <vector> #include <cstring> using namespace std; const int maxn=1005; const int INF=1e9; int n,m,dist[maxn],pre[maxn];bool vis[maxn]; struct node{ int v,w;node(){};node(int v,int w):v(v),w(w){}; }; bool cmp(node a,node b){ return a.v<b.v; } vector<node> G[maxn]; vector<node> St; void init(){ for(int i=0;i<maxn;++i) G[i].clear();St.clear(); for(int i=0;i<maxn;++i) dist[i]=INF; memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); } int main(){ int T;scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); init();int a,b,c; for(int i=0;i<m;++i){ scanf("%d%d%d",&a,&b,&c); G[b].push_back(node(a,c)); if(a==0) St.push_back(node(b,c)); //G[b].push_back(node(a,c)); } queue<int> Q;Q.push(n+1);vis[n+1]=1;dist[n+1]=0; while(Q.size()){ int now=Q.front();Q.pop();vis[now]=0; for(int i=0;i<G[now].size();++i){ int to=G[now][i].v,tw=G[now][i].w; if(dist[to]>dist[now]+tw){ dist[to]=dist[now]+tw; pre[to]=now; if(!vis[to]) { Q.push(to);vis[to]=1; } } } } if(dist[0]==INF) { printf("-1\n");continue; } int flag=0,ans=INF; for(int i=0;i<St.size();++i){ int to=St[i].v,tw=St[i].w; if(tw+dist[to]==dist[0]){ if(to==n+1){ flag=1;break; } ans=min(ans,to); } } if(flag) printf("0\n"); else printf("%d\n",ans); } return 0; }
下面这种做法是错误做法，那就是先对每个邻接表按顶点标号大小排序，然后跑一遍spfa
一般的数据都能正常出解，但是对于这一组数据，哈哈，怕是翻车了
2 4
0 1 2
1 2 1
0 2 3
2 3 1
松弛完1，直接松弛0,2这条边，于是0,1,2,3这条路径不会被考虑了，
于是答案就是2，而不是正确的1,1被早来的0,2这条边从后面架空了
附上错误代码
#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <vector> #include <cstring> using namespace std; const int maxn=1005; const int INF=1e9; int n,m,dist[maxn],pre[maxn];bool vis[maxn]; struct node{ int v,w;node(){};node(int v,int w):v(v),w(w){}; }; bool cmp(node a,node b){ return a.v<b.v; } vector<node> G[maxn]; void init(){ for(int i=0;i<maxn;++i) G[i].clear(); for(int i=0;i<maxn;++i) dist[i]=INF; memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); } int main(){ int T;scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); init();int a,b,c; for(int i=0;i<m;++i){ scanf("%d%d%d",&a,&b,&c); G[a].push_back(node(b,c)); //G[b].push_back(node(a,c)); } for(int i=0;i<maxn;++i){ if(G[i].size()) sort(G[i].begin(),G[i].end(),cmp); } queue<int> Q;Q.push(0);vis[0]=1;dist[0]=0; while(Q.size()){ int now=Q.front();Q.pop();vis[now]=0; for(int i=0;i<G[now].size();++i){ int to=G[now][i].v,tw=G[now][i].w; if(dist[to]>dist[now]+tw){ dist[to]=dist[now]+tw; pre[to]=now; if(!vis[to]) { Q.push(to);vis[to]=1; } } } } if(dist[n+1]==INF) { printf("-1\n");continue; } int i; for(i=0;i<G[0].size();++i) { if(G[0][i].v==n+1&&G[0][i].w==dist[n+1]) break; } if(i<G[0].size()) {printf("0\n");continue;} for(i=n+1;pre[i]!=0;i=pre[i]); printf("%d\n",i); } return 0; }
由于路径不算原点，所以说
0 2 3>0 1 2 3
也就是 2 3>1 2 3
所以在源点需要特判
sdut3562-求字典序最小的最短路 按顶点排序后spfa的反例
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。