感觉把POJ最短路都刷了刷，大概分了几类
1 裸体最短路
poj1847 注意题意 每个站对应的第一个位置是不用搬轨道的，其他的都是用搬一下
然后直接跑
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N=105,M=N*N*2; int head[N],list[M],nxt[M],len[M],tot; int n,ss,tt; void add(int a,int b,int c) { tot++; list[tot]=b,len[tot]=c; nxt[tot]=head[a]; head[a]=tot; } int dist[N],vis[N]; int spfa(int s,int t) { queue<int>q;q.push(s); memset(dist,0x3f,sizeof dist); dist[s]=0;memset(vis,0,sizeof vis); while(!q.empty()) { int v=q.front();q.pop();vis[v]=0; for(int i=head[v];i;i=nxt[i]) { int u=list[i]; if(dist[u]>dist[v]+len[i]) { dist[u]=dist[v]+len[i]; if(!vis[u]) { vis[u]=1;q.push(u); } } } } return dist[t]; } int main() { scanf("%d%d%d",&n,&ss,&tt); for(int i=1;i< =n;i++) { int x;scanf("%d",&x); for(int j=1;j<=x;j++) { int t;scanf("%d",&t); if(j==1)add(i,t,0); else add(i,t,1); } } int ans=spfa(ss,tt); if(ans!=0x3f3f3f3f)cout<<ans<<endl; else puts("-1"); }
2 来回的最短路
poj 2387
要想知道去和回来（形成一个环）的最短路，跑一遍正向图，再跑一遍反向就行了。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1005,M=100005; int head[N],nxt[M],list[M],len[M],tot; int a[M],b[M],c[M]; bool vis[N]; int dist[N],d[N],n,m,ss; void add(int a,int b,int c) { tot++; list[tot]=b,len[tot]=c; nxt[tot]=head[a]; head[a]=tot; } void spfa(int s) { memset(dist,0x3f,sizeof dist); memset(vis,0,sizeof vis); dist[s]=0; queue<int>q;q.push(s);vis[s]=1; while(!q.empty()) { int v=q.front();q.pop();vis[v]=0; for(int i=head[v];i;i=nxt[i]) { int u=list[i]; if(dist[u]>dist[v]+len[i]) { dist[u]=dist[v]+len[i]; if(!vis[u]) q.push(u),vis[u]=1; } } } } int main() { scanf("%d%d%d",&n,&m,&ss); for(int i=1;i< =m;i++) { scanf("%d%d%d",&a[i],&b[i],&c[i]); add(a[i],b[i],c[i]); } spfa(ss); for(int i=1;i<=n;i++)d[i]=dist[i]; memset(head,0,sizeof head);tot=0; for(int i=1;i<=m;i++)add(b[i],a[i],c[i]); spfa(ss);int ans=0; for(int i=1;i<=n;i++) ans=max(ans,d[i]+dist[i]); printf("%d\n",ans); }
3 路径上的最大/小值
这类问题一般都是求一条路径 要求在路径上某边的权值最大值最小 或最小值最大
以最小值最大为例
我们改变一下dist数组的定义：dist[i]定义为从原点到点i路径上权值最小值的最大值。
然后松弛条件改为dist[u]=max(dist[u],min(dist[v],len[i]));
于是跑dij或者spfa都可以了
poj1797 便是最大值最小
（spfa比dij慢一点，在这道题上)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; const int N=3005,M=2*N*N+5; int head[N],nxt[M],list[M],len[M],tot; int dist[N],n,m; void add(int a,int b,int c) { tot++; list[tot]=b,len[tot]=c; nxt[tot]=head[a]; head[a]=tot; } struct edge { int d,x; edge(){} edge(int a,int b){d=a,x=b;} friend bool operator< (edge n1, edge n2) { return n1.d<n2.d;//从最大排到最小 } }; void dij() { memset(dist,-0x3f,sizeof dist); priority_queue<edge>q; for(int i=head[1];i;i=nxt[i]) q.push(edge(len[i],list[i])),dist[list[i]]=len[i]; while(!q.empty()) { edge now=q.top();q.pop(); int v=now.x; if(now.d<dist [v])continue; for(int i=head[v];i;i=nxt[i]) { int u=list[i]; if(dist[u]<min(dist[v],len[i])) { dist[u]=min(dist[v],len[i]); q.push(edge(dist[u],u)); } } } } int main() { int t,cnt=0;scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(head,0,sizeof head);tot=0; for(int i=1;i<=m;i++) { int a,b,c;scanf("%d%d%d",&a,&b,&c); add(a,b,c),add(b,a,c); } dij(); printf("Scenario #%d:\n",++cnt); printf("%d\n",dist[n]); puts(""); } return 0; }
4 spfa判环
在spfa中，某一个点最多进队出队n-1次（bellman-ford算法，全松弛完毕执行n-1次循环）
倘若进队出队超过n-1次，说明出现了负(正)环。
poj2240 一个汇率问题
典型的判环，边上的权值乘一下dist即可完成松弛时的汇率计算
（记得把初始时的钱加多点）
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<map> #include<string> using namespace std; const int N=50,M=N*N*2; map</string><string ,int>hash; int head[N],nxt[M],list[M],tot; int n,m; double len[M]; void add(int a,int b,double c) { tot++; list[tot]=b,len[tot]=c; nxt[tot]=head[a]; head[a]=tot; } int use[N],vis[N]; double dist[N]; bool spfa() { queue<int>q; memset(dist,0,sizeof dist); memset(vis,0,sizeof vis); memset(use,0,sizeof use); dist[1]=100000; q.push(1);use[1]++; while(!q.empty()) { int v=q.front();q.pop();vis[v]=0; for(int i=head[v];i;i=nxt[i]) { int u=list[i]; if(dist[u]<dist [v]*len[i]) { dist[u]=dist[v]*len[i]; if(!vis[u]) { vis[u]=1;q.push(u);use[u]++; if(use[u]>n-1) return 1; } } } } return 0; } int main() { int cnt=0; while(1) { scanf("%d",&n); if(n==0)return 0; memset(head,0,sizeof head);tot=0; hash.clear(); for(int i=1;i< =n;i++) { string t;cin>>t; hash[t]=i; } scanf("%d",&m); for(int i=1;i< =m;i++) { string t1,t2;double x; cin>>t1>>x>>t2; add(hash[t1],hash[t2],x); } printf("Case %d: ",++cnt); puts(spfa()?"Yes":"No"); } } </dist></int></string></map></algorithm></queue></cstring></cstdio></iostream>
poj1860 另一个汇率问题
在这道题上我们耍了个小伎俩，只需要每次判断dist[1]是不是变大了即可
【滑稽】
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1050; const double eps=1e-7; int head[N],nxt[N*N*2],list[N*N*2],tot; double len[N*N*2],slen[N*N*2]; void add(int a,int b,double c,double d) { tot++; list[tot]=b,len[tot]=c,slen[tot]=d; nxt[tot]=head[a]; head[a]=tot; } bool vis[N]; int n,m,s;double t; double dist[N]; bool spfa() { queue<int>q; dist[s]=t; q.push(s);vis[s]=1; while(!q.empty()) { int v=q.front();q.pop();vis[v]=0; for(int i=head[v];i;i=nxt[i]) { int u=list[i]; if(dist[u]< (dist[v]-slen[i])*len[i]) { dist[u]=(dist[v]-slen[i])*len[i]; if(!vis[u]) q.push(u),vis[u]=1; } if(u==s&&dist[u]>t)return 1; } } return 0; } int main() { cin>>n>>m>>s>>t; for(int i=1;i< =m;i++) { int a,b; double c,d,e,f; cin>>a>>b>>c>>d>>e>>f; add(a,b,c,d); add(b,a,e,f); } puts(spfa()?"YES":"NO"); } </int></queue></algorithm></cstring></cstdio></iostream>
4 floyd传递闭包
floyd可以很快的完成闭包传递，但是最快的方法好像是bitset
这个很简单，就略过了，附上之前的某个链接
https://icebound.cc/2015/08/01/stdbitset.html
n^2的传递闭包↑
5 带条件的最短路
poj 1062 昂贵的聘礼
这可能属于带条件的最短路？
这题比较有意思 枚举可以交易的等级范围，再跑最短路，在最短路上严格限定刚刚枚举的等级
不过注意一个问题，枚举时记得注意细节！
细节细节细节！
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N=200,M=N*N*3; int head[N],list[M],nxt[M],len[M],tot; int m,n,le[N]; void add(int a,int b,int c) { tot++; list[tot]=b,len[tot]=c; nxt[tot]=head[a]; head[a]=tot; } int dist[N],vis[N]; int spfa(int l,int r) { queue<int>q;q.push(0); memset(dist,0x3f,sizeof dist); dist[0]=0;memset(vis,0,sizeof vis); while(!q.empty()) { int v=q.front();q.pop();vis[v]=0; for(int i=head[v];i;i=nxt[i]) { int u=list[i]; if(le[u]>=l&&le[u]< =r) { if(dist[u]>dist[v]+len[i]) { dist[u]=dist[v]+len[i]; if(!vis[u]) { vis[u]=1;q.push(u); } } } } } return dist[1]; } int main() { scanf("%d%d",&m,&n); int ll=0x3f3f3f3f,rr=-0x3f3f3f3f; for(int i=1;i< =n;i++) { int x,y;scanf("%d%d%d",&x,&le[i],&y); ll=min(ll,le[i]),rr=max(rr,le[i]); add(0,i,x); for(int j=1;j<=y;j++) { int a,b; scanf("%d%d",&a,&b); add(a,i,b); } } int ans=0x3f3f3f3f; for(int i=ll;i<=rr;i++) { int x=i+m; ans=min(ans,spfa(i,x)); if(i+m>rr)break; } printf("%d\n",ans); return 0; } </int></queue></cstring></algorithm></cstdio></iostream>
6 关于最短路的补充
我现在对于dij spfa(bellman-ford)和floyd的理解又改变了
感觉dij像是一个变种bfs算法，spfa是一种对边进行枚举的最短路算法，floyd是一种dp
以后还会再更新吧？