這題的話，坑點挺多的，我也WA了好幾次。
首先，對于map，因為是多次使用，所以每次處理完一個圖之后就要清空。

其次，就是對于DIjkstra跑圖的時候，如果這個圖是連通圖的話，我們每次選取最小值點是一定可以選到的，但是對于不連通的圖，如果任何一個點都不與終點連通，那選取最小值點的時候就一定會選到無窮大點。
所以這時候，如果不對我們之前聲明的用來存最小值點標號的變量k賦初值的話，那基本上訪問是越界的，k里面的數(shù)原本基本上都是幾十萬，所以我就一直越界啦~
要么就把最小值等于無窮的時候，直接跳出，也是可以的，然后再對vis標記，這樣跳出就不會越界了。

而且其實cin讀入還挺快的，因為用的是string類，所以用cin讀入了，其實直接用scanf讀入字符串也是可的。如果關(guān)閉cin和stdio的同步，這cin讀入相當快。

#include <iostream> #include <cstring> #include <string> #include <map> using namespace std; const int INF = 1 << 30; int n,cnt,flag,t; int w[160][160]; int d[160]; bool vis[160]; map<string, int> name;void Dijkstra() {memset(vis, false, sizeof(vis));for (int i = 1; i <= cnt;i++) {d[i] = w[1][i];}vis[1] = 1;d[1] = 0;for (int i = 1; i < cnt; i++){int m=INF, k=0;for (int j = 1; j <= cnt; j++){if (!vis[j] &&m>d[j]) {m=d[j];k = j;}}if (m==INF)break;vis[k] = 1;for (int j = 1; j <= cnt;j++) {if (!vis[j]&&d[j]>d[k]+w[k][j]) {d[j] = d[k] + w[k][j];}}} }int main() {ios::sync_with_stdio(false);while (cin>>n&&n!=-1) {if (n==0) {cout << -1 << endl;continue;}for (int i = 0; i < 160;i++) {for (int j = 0; j < 160;j++) {w[i][j] = INF;}}name.clear();cnt = 1;flag = 0;string s, e;cin >> s >> e;if (s==e)flag = 1;name[s] = cnt++;name[e] = cnt++;while (n--) {cin >> s >> e >> t;if (!name[s])name[s] = cnt++;if (!name[e])name[e] = cnt++;if (w[name[s]][name[e]]>t) {w[name[s]][name[e]] = t;w[name[e]][name[s]] = t;}}if (flag) {cout << 0 << endl;continue;}cnt--;Dijkstra();if (d[2]==INF)cout << -1 << endl;elsecout << d[2] << endl;}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/xyqxyq/p/10350138.html

總結(jié)

以上是生活随笔為你收集整理的HDU-2112-HDU Today的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。