The bus system of City X is quite strange. Unlike other city’s system, the cost of ticket is calculated based on the distance between the two stations. Here is a list which describes the relationship between the distance and the cost.
Your neighbor is a person who is a really miser. He asked you to help him to calculate the minimum cost between the two stations he listed. Can you solve this problem fZ http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vciBoaW0/PGJyPgpUbyBzaW1wbGlmeSB0aGlzIHByb2JsZW0sIHlvdSBjYW4gYXNzdW1lIHRoYXQgYWxsIHRoZSBzdGF0aW9ucyBhcmUgbG9jYXRlZCBvbiBhIHN0cmFpZ2h0IGxpbmUuIFdlIHVzZSB4LWNvb3JkaW5hdGVzIHRvIGRlc2NyaWJlIHRoZSBzdGF0aW9uc6GvIHBvc2l0aW9ucy48YnI+CgogCjxicj4KSW5wdXQKVGhlIGlucHV0IGNvbnNpc3RzIG9mIHNldmVyYWwgdGVzdCBjYXNlcy4gVGhlcmUgaXMgYSBzaW5nbGUgbnVtYmVyIGFib3ZlIGFsbCwgdGhlIG51bWJlciBvZiBjYXNlcy4gVGhlcmUgYXJlIG5vIG1vcmUgdGhhbiAyMCBjYXNlcy48YnI+CkVhY2ggY2FzZSBjb250YWlucyBlaWdodCBpbnRlZ2VycyBvbiB0aGUgZmlyc3QgbGluZSwgd2hpY2ggYXJlIEwxLCBMMiwgTDMsIEw0LCBDMSwgQzIsIEMzLCBDNCwgZWFjaCBudW1iZXIgaXMgbm9uLW5lZ2F0aXZlIGFuZCBub3QgbGFyZ2VyIHRoYW4gMSwwMDAsMDAwLDAwMC4gWW91IGNhbiBhbHNvIGFzc3VtZSB0aGF0IEwxPD1MMjw9TDM8PUw0Ljxicj4KVHdvIGludGVnZXJzLCBuIGFuZCBtLCBhcmUgZ2l2ZW4gbmV4dCwgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgdGhlIHN0YXRpb25zIGFuZCBxdWVzdGlvbnMuIEVhY2ggb2YgdGhlIG5leHQgbiBsaW5lcyBjb250YWlucyBvbmUgaW50ZWdlciwgcmVwcmVzZW50aW5nIHRoZSB4LWNvb3JkaW5hdGUgb2YgdGhlIGl0aCBzdGF0aW9uLiBFYWNoIG9mIHRoZSBuZXh0IG0gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzLCByZXByZXNlbnRpbmcgdGhlIHN0YXJ0CiBwb2ludCBhbmQgdGhlIGRlc3RpbmF0aW9uLjxicj4KSW4gYWxsIG9mIHRoZSBxdWVzdGlvbnMsIHRoZSBzdGFydCBwb2ludCB3aWxsIGJlIGRpZmZlcmVudCBmcm9tIHRoZSBkZXN0aW5hdGlvbi48YnI+CkZvciBlYWNoIGNhc2UsMjw9Tjw9MTAwLDA8PU08PTUwMCwgZWFjaCB4LWNvb3JkaW5hdGUgaXMgYmV0d2VlbiAtMSwwMDAsMDAwLDAwMCBhbmQgMSwwMDAsMDAwLDAwMCwgYW5kIG5vIHR3byB4LWNvb3JkaW5hdGVzIHdpbGwgaGF2ZSB0aGUgc2FtZSB2YWx1ZS48YnI+CgogCjxicj4KT3V0cHV0CkZvciBlYWNoIHF1ZXN0aW9uLCBpZiB0aGUgdHdvIHN0YXRpb25zIGFyZSBhdHRhaW5hYmxlLCBwcmludCB0aGUgbWluaW11bSBjb3N0IGJldHdlZW4gdGhlbS4gT3RoZXJ3aXNlLCBwcmludCChsFN0YXRpb24gWCBhbmQgc3RhdGlvbiBZIGFyZSBub3QgYXR0YWluYWJsZS6hsSBVc2UgdGhlIGZvcm1hdCBpbiB0aGUgc2FtcGxlLjxicj4KCiAKPGJyPgpTYW1wbGUgSW5wdXQKCjxwcmUgY2xhc3M9"brush:java;">2 1 2 3 4 1 3 5 7 4 2 1 2 3 4 1 4 4 1 1 2 3 4 1 3 5 7 4 1 1 2 3 10 1 4
Sample Output
Case 1: The minimum cost between station 1 and station 4 is 3. The minimum cost between station 4 and station 1 is 3. Case 2: Station 1 and station 4 are not attainable. 这道题开始一直在错- -原来是我inf设置得还是小了，开始设置的是inf = 2,000,000,000后来改成1e18才过- -蛋疼#include#include #include using namespace std; const __int64 inf = 1e18; __int64 map[105][105]; __int64 k[105]; __int64 a[5]; __int64 c[5]; __int64 n,m; __int64 judge(__int64 x) { if(x>0 && x<=a[1]) return c[1]; if(x<=a[2]) return c[2]; if(x<=a[3]) return c[3]; if(x<=a[4]) return c[4]; return inf; } __int64 kabs(__int64 a) { return a<0 -a:a; } void floyd() { __int64 i,j,k; for(k = 1; k<=n; k++) for(i = 1; i<=n; i++) for(j = 1; j<=n; j++) if(map[i][j]>map[i][k]+map[k][j]) map[i][j] = map[i][k]+map[k][j]; } int main() { __int64 t,i,j,x,y,cas = 1; scanf("%I64d",&t); while(t--) { for(i = 1; i<=4; i++) scanf("%I64d",&a[i]); for(i = 1; i<=4; i++) scanf("%I64d",&c[i]); scanf("%I64d%I64d",&n,&m); for(i = 1; i<=n; i++) scanf("%I64d",&k[i]); for(i = 0; i<=n; i++) { for(j = 0; j<=n; j++) map[i][j] = inf; map[i][i] = 0; } for(i = 1; i<=n; i++) for(j = i; j<=n; j++) { map[i][j] = map[j][i] = judge(kabs(k[j]-k[i])); } floyd(); printf("Case %I64d:\n",cas++); while(m--) { scanf("%I64d%I64d",&x,&y); if(map[x][y] == inf) printf("Station %I64d and station %I64d are not attainable.\n",x,y); else printf("The minimum cost between station %I64d and station %I64d is %I64d.\n",x,y,map[x][y]); } } return 0; }