题目描述：

 

在一个有向图有n个顶点（编号从1到n），给一个起点s，问从起点出发，至少经过一条边，回到起点的最短距离。

 

 

输入：

 

输入包括多组，每组输入第一行包括三个整数n,m,s（1<=n<=500,0<=m<=10000,1<=s<=n），接下来有m行，每行包括三个整数a,b,c(1<=a,b<=n,1<=c<=1000)，表示有一条a到b的边，长度为c。

 

 

输出：

 

对每组输入。输出最短距离，如果没有这个一条路径输出"help!"。

 

 

 

 

样例输入：

5 6 11 2 12 3 23 4 14 5 13 1 34 1 1

样例输出：

5

看网上的做法，都使用迪杰斯特拉算法做的，而我采用的是广度优先搜索的办法
但一开始的代码提交错误，如下

 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <queue> 5 #include <vector> 6 using namespace std; 7   8 int n,m,s; 9 queue <int> que;10 typedef pair<int, int> Edge;11 vector<Edge> edge[502];12 int step[502];13  14 int main(int argc, char const *argv[])15 {16     while(scanf("%d %d %d",&n,&m,&s) != EOF) {17         while(!que.empty()) {18             que.pop();19         }20         for(int i = 0; i < n; i++) {21             edge[i].clear();22         }23         memset(step, 0, sizeof(step));24         while(m--) {25             int a, b, d;26             scanf("%d %d %d",&a,&b,&d);27             edge[a].push_back(Edge(b,d));28         }29         que.push(s);30         while(!que.empty()) {31             int p = que.front();que.pop();32             int sizep = edge[p].size();33  34             for(int i = 0; i < sizep; i++) {35                 int tp = edge[p][i].first;36                 int ct = edge[p][i].second;37                 int pt = step[p] + ct;38                 if(step[tp] == 0 || pt < step[tp]) {39                     step[tp] = pt;40                     que.push(tp);41                 }42             }43         }44         if(step[s] == 0) {45             puts("help!");46         }47         else {48             printf("%d\n",step[s]);49         }50     }51     return 0;52 }

这段代码犯了两个错误，一是20行, clear不应该只到n，万一第二次输入的n比第一次的n小呢?

第二是题目中有 起点s到起点s的边，需要特殊处理，代码如下

 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <queue> 5 #include <vector> 6 using namespace std; 7  8 int n,m,s; 9 queue <int> que;10 typedef pair<int, int> Edge;11 vector<Edge> edge[502];12 int step[502];13 14 int main(int argc, char const *argv[])15 {16     freopen("input.txt","r",stdin);17     while(scanf("%d %d %d",&n,&m,&s) != EOF) {18         while(!que.empty()) {19             que.pop();20         }21         for(int i = 0; i < 502; i++) {22             edge[i].clear();23         }24         memset(step, 0, sizeof(step));25         while(m--) {26             int a, b, d;27             scanf("%d %d %d",&a,&b,&d);28             edge[a].push_back(Edge(b,d));29         }30         que.push(s);31         while(!que.empty()) {32             int p = que.front();que.pop();33             int sizep = edge[p].size();34 35             for(int i = 0; i < sizep; i++) {36                 int tp = edge[p][i].first;37                 int ct = edge[p][i].second;38                 int pt = step[p] + ct;39                 if(p == s) {40                     pt = ct;41                 }42                 if(step[tp] == 0 || pt < step[tp]) {43                     step[tp] = pt;44                     que.push(tp);45                 }46             }47         }48         if(step[s] == 0) {49             puts("help!");50         }51         else {52             printf("%d\n",step[s]);53         }54     }55     return 0;56 }

 

九度oj 题目1411：转圈