Bus System
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Problem Description Because of the huge population of China, public transportation is very important. Bus is an important transportation method in traditional public transportation system. And it’s still playing an important role even now.
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+CgoKIAo8YnI+CgpJbnB1dAoKVGhlIGlucHV0IGNvbnNpc3RzIG9mIHNldmVyYWwgdGVzdCBjYXNlcy4gVGhlcmUgaXMgYSBzaW5nbGUgbnVtYmVyIGFib3ZlIGFsbCwgdGhlIG51bWJlciBvZiBjYXNlcy4gVGhlcmUgYXJlIG5vIG1vcmUgdGhhbiAyMCBjYXNlcy48YnI+CkVhY2ggY2FzZSBjb250YWlucyBlaWdodCBpbnRlZ2VycyBvbiB0aGUgZmlyc3QgbGluZSwgd2hpY2ggYXJlIEwxLCBMMiwgTDMsIEw0LCBDMSwgQzIsIEMzLCBDNCwgZWFjaCBudW1iZXIgaXMgbm9uLW5lZ2F0aXZlIGFuZCBub3QgbGFyZ2VyIHRoYW4gMSwwMDAsMDAwLDAwMC4gWW91IGNhbiBhbHNvIGFzc3VtZSB0aGF0IEwxPD1MMjw9TDM8PUw0Ljxicj4KVHdvIGludGVnZXJzLCBuIGFuZCBtLCBhcmUgZ2l2ZW4gbmV4dCwgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgdGhlIHN0YXRpb25zIGFuZCBxdWVzdGlvbnMuIEVhY2ggb2YgdGhlIG5leHQgbiBsaW5lcyBjb250YWlucyBvbmUgaW50ZWdlciwgcmVwcmVzZW50aW5nIHRoZSB4LWNvb3JkaW5hdGUgb2YgdGhlIGl0aCBzdGF0aW9uLiBFYWNoIG9mIHRoZSBuZXh0IG0gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzLCByZXByZXNlbnRpbmcgdGhlIHN0YXJ0CiBwb2ludCBhbmQgdGhlIGRlc3RpbmF0aW9uLjxicj4KSW4gYWxsIG9mIHRoZSBxdWVzdGlvbnMsIHRoZSBzdGFydCBwb2ludCB3aWxsIGJlIGRpZmZlcmVudCBmcm9tIHRoZSBkZXN0aW5hdGlvbi48YnI+CkZvciBlYWNoIGNhc2UsMjw9Tjw9MTAwLDA8PU08PTUwMCwgZWFjaCB4LWNvb3JkaW5hdGUgaXMgYmV0d2VlbiAtMSwwMDAsMDAwLDAwMCBhbmQgMSwwMDAsMDAwLDAwMCwgYW5kIG5vIHR3byB4LWNvb3JkaW5hdGVzIHdpbGwgaGF2ZSB0aGUgc2FtZSB2YWx1ZS48YnI+CgoKIAo8YnI+CgpPdXRwdXQKCkZvciBlYWNoIHF1ZXN0aW9uLCBpZiB0aGUgdHdvIHN0YXRpb25zIGFyZSBhdHRhaW5hYmxlLCBwcmludCB0aGUgbWluaW11bSBjb3N0IGJldHdlZW4gdGhlbS4gT3RoZXJ3aXNlLCBwcmludCChsFN0YXRpb24gWCBhbmQgc3RhdGlvbiBZIGFyZSBub3QgYXR0YWluYWJsZS6hsSBVc2UgdGhlIGZvcm1hdCBpbiB0aGUgc2FtcGxlLjxicj4KCgogCjxicj4KClNhbXBsZSBJbnB1dAoKPHByZSBjbGFzcz0="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.这道题本身并不难，WA两次之后才发现INF设的太小了，改成INF=1e18后，直接AC。
#include#include #define INF 1e18 const int N = 110; __int64 x[510], w[N][N], d[N]; __int64 abs(__int64 x) { return x >= 0 x : -x; } void Dijkstra(__int64 n, __int64 u) { int vis[N]; __int64 i; memset(vis, 0, sizeof(vis)); for(i = 1; i <= n; i++) d[i] = INF; d[u] = 0; for(i = 1; i <= n; i++) { __int64 x = u, temp = INF; for(__int64 y = 1; y <= n; y++) if(!vis[y] && d[y] < temp) temp = d[x = y]; if(temp == INF) break; vis[x] = 1; for(__int64 y = 1; y <= n; y++) if(d[y] > d[x] + w[x][y]) d[y] = d[x] + w[x][y]; } } int main() { __int64 T, n, m, i, j, cas = 0; __int64 l[5], c[5]; scanf("%I64d",&T); while(T--) { for(i = 1;