本文共 2416 字，大约阅读时间需要 8 分钟。
SPFA.注意状态转移条件，ans的求解需要在bfs中间求解。因为只要到了地点n，则无需等待其他tourist。
1 /* 229B */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set 25 #define stpii set > 26 #define mpii map 27 #define vi vector 28 #define pii pair 29 #define vpii vector > 30 #define rep(i, a, n) for (int i=a;i =a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 42 const int maxn = 1e5+5; 43 const int INF = 0x3f3f3f3f; 44 vpii E[maxn]; 45 vpii T[maxn]; 46 int dis[maxn]; 47 bool visit[maxn]; 48 int a[maxn], b[maxn]; 49 50 int main() { 51 ios::sync_with_stdio(false); 52 #ifndef ONLINE_JUDGE 53 freopen("data.in", "r", stdin); 54 freopen("data.out", "w", stdout); 55 #endif 56 57 int n, m; 58 int u, v, w; 59 60 scanf("%d %d", &n, &m); 61 while (m--) { 62 scanf("%d %d %d", &u, &v, &w); 63 E[u].pb(mp(v, w)); 64 E[v].pb(mp(u, w)); 65 } 66 rep(i, 1, n+1) { 67 scanf("%d", &m); 68 rep(j, 1, m+1) 69 scanf("%d", &a[j]); 70 b[m] = 1; 71 per(j, 1, m) { 72 if (a[j]+1 == a[j+1]) 73 b[j] = b[j+1] + 1; 74 else 75 b[j] = 1; 76 } 77 rep(j, 1, m+1) 78 T[i].pb(mp(a[j], b[j])); 79 } 80 81 int i, tmp; 82 int ans = INF; 83 pii p(0, 0); 84 vpii::iterator iter; 85 queue Q; 86 Q.push(1); 87 memset(dis, 0x3f, sizeof(dis)); 88 // may be have 0 in T[1] 89 iter = upper_bound(all(T[1]), p); 90 if (iter!=T[1].end() && iter->fir==0) { 91 dis[1] = iter->sec; 92 } else { 93 dis[1] = 0; 94 } 95 visit[1] = true; 96 97 while (!Q.empty()) { 98 u = Q.front(); 99 Q.pop();100 visit[u] = false;101 for (i=0; i fir==tmp) {110 tmp += iter->sec;111 }112 if (tmp < dis[v]) {113 dis[v] = tmp;114 if (!visit[v]) {115 visit[v] = true;116 Q.push(v);117 }118 }119 }120 }121 122 ans = ans==INF ? -1:ans;123 printf("%d\n", ans);124 125 #ifndef ONLINE_JUDGE126 printf("time = %d.\n", (int)clock());127 #endif128 129 return 0;130 }
转载于:https://www.cnblogs.com/bombe1013/p/4640814.html