题意 ： 一个司机要从1点到达n点，1点到n点中有一些点有宾馆，司机的最长开车时间不能超过10小时，所以要在10小时之内找到宾馆休息，但是为了尽快的走到n点，问最少可以经过几个宾馆。
思路 ： 这个题太狠了，简直不是人做的。。。。可以BFS一下，然后在B之前先D一下能走的路。当然也可以用SPFA+Floyd。
#include <stdio.h> #include <string.h> #include <iostream> #include <queue> #include <vector> using namespace std ; struct node { int u,w ; }temp ; struct BFS { int u,w,step ; }t,t1 ; const int maxn = 10110 ; const int INF = 999999999 ; vector<node> vec[maxn] ; queue<BFS>Q ; bool hashh[10110],vis[maxn] ; int n,m,h ; int ret[maxn],st[maxn] ; void DFS(int u,int w,int step) { if(vis[u]) return ; if(w >= ret[u]) return ; if(w > 0) ret[u] = w ; if(hashh[u] && w == 0) vis[u] = true ; for(int i = 0 ; i < vec[u].size() ; i++) { if(hashh[vec[u][i].u] && (!vis[vec[u][i].u]) && (w+vec[u][i].w<=600) && (step + 1 < st[vec[u][i].u])) { t.u = vec[u][i].u ; //t.w = vec[u][i].w ; t.step = step+1 ; st[t.u] = t.step ; Q.push(t) ; } if(w+vec[u][i].w <= 600) DFS(vec[u][i].u,w+vec[u][i].w,step) ; } } void BFS() { while(!Q.empty()) Q.pop() ; t.u = 1 ; t.w = t.step = 0 ; Q.push(t) ; while(!Q.empty()) { t1 = Q.front() ; Q.pop() ; if(t1.u == n) { printf("%d ",t1.step-1) ; return ; } DFS(t1.u,0,t1.step) ; } printf("-1 ") ; return ; } int main() { while(~scanf("%d",&n)) { if(n == 0) break ; for(int i = 0 ; i <= n ; i++) { vector<node>().swap(vec[i]) ; ret[i] = st[i] = INF ; hashh[i] = vis[i] = false ; } hashh[1] = hashh[n] = true ; scanf("%d",&m) ; int s ; for(int i = 0 ; i < m ; i++) { scanf("%d",&s) ; hashh[s] = true ; } scanf("%d",&h) ; int u,v,w ; for(int i = 0 ; i < h ; i++) { scanf("%d %d %d",&u,&v,&w) ; temp.u = v ; temp.w = w ; vec[u].push_back(temp) ; temp.u = u ; vec[v].push_back(temp) ; } BFS() ; } return 0 ; }
#include <cstdio> #include <cstring> #include <map> #include <vector> #include <queue> #define maxn 200 #include <algorithm> using namespace std; const int inf=0x3fffffff; struct node { int v,cost; }; int g[maxn][maxn],a[maxn],dis[20000]; int n,m,k; map<int,int>q; vector<node>v[20000]; bool vis[20000]; int que[20000]; void inti() { q.clear(); for(int i=0; i<=n; i++) { v.clear(); } for(int i=0; i<=m+2; i++) { for(int j=0; j<=m+2; j++) { g[j]=inf; if(i==j) g[j]=0; } } } void spfa(int qr) { queue<int>qq; memset(vis,false,sizeof(vis)); for(int i=1; i<=n; i++) dis=inf; dis[qr]=0; qq.push(qr); vis[qr]=true; while(!qq.empty()) { int x=qq.front(); qq.pop(); vis[x]=false; for(int i=0; i<(int)v[x].size(); i++) { int v2=v[x].v,cost=v[x].cost; if(dis[v2]>dis[x]+cost) { dis[v2]=dis[x]+cost; if(!vis[v2]) { vis[v2]=true; qq.push(v2); } } } } for(int i=1; i<=n; i++) { if(dis<=600&&q!=0) { g[q[qr]][q]=1; } } } void floyd() { for(int c=0; c<=m+1; c++) { for(int i=0; i<=m+1; i++) { for(int j=0; j<=m+1; j++) { g[j]=min(g[j],g[c]+g[c][j]); } } } } int main() { while(scanf("%d",&n)!=EOF) { if(n==0) break; scanf("%d",&m); inti(); for(int i=1; i<=m; i++) { scanf("%d",&a); q[a]=i; } a[0]=1; q[1]=0; a[m+1]=n; q[n]=m+1; scanf("%d",&k); for(int i=0; i<k; i++) { int u,v1,cost; scanf("%d%d%d",&u,&v1,&cost); node st; st.v=v1; st.cost=cost; node st1; st1.v=u; st1.cost=cost; v.push_back(st); v[v1].push_back(st1); } for(int i=0; i<=m; i++) { spfa(a); } floyd(); if(g[0][m+1]==inf) { printf("-1 "); } else printf("%d ",g[0][m+1]-1); } return 0; }
二货写的SPFA+Floyd