/* n个点，m条边，求1 - n 的距离 输入x y z，表示x到y的距离为z 不存在输出-1 */ #include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; #define INF 0x3f3f3f3f struct Pair { int first,second; //first存点，second存距离 bool friend operator < (Pair a,Pair b) { return a.second > b.second; } }pr,ne; int n,m; vector<int> edge[105]; //存与之相连的边 int length[105][105]; //存相连边的长度 int dis[105]; //记录到起点的距离 void dijkstra() { memset(dis,INF,sizeof(dis)); /* 第二个参数可以填 0，-1，1，其他 0：把元素都初始化为0 -1：初始化为-1 1：初始化为一个奇怪的值 其他：其他 */ bool vis[105]; memset(vis,false,sizeof(vis)); dis[1] = 0; pr.first = 1; pr.second = 0; priority_queue<Pair> Q; Q.push(pr); while (!Q.empty()) { pr = Q.top(); // printf ("==%d %d==\n",pr.first,pr.second); Q.pop(); if (vis[pr.first]) continue; vis[pr.first] = true; for (int i = 0 ; i < edge[pr.first].size() ; i++) { ne.first = edge[pr.first][i]; ne.second = pr.second + length[pr.first][ne.first]; if (ne.second < dis[ne.first]) { dis[ne.first] = ne.second; Q.push(ne); } } } } int main() { scanf ("%d%d",&n,&m); memset(length,-1,sizeof(length)); for (int i = 1 ; i <= m ; i++) { int x,y,z; scanf ("%d%d%d",&x,&y,&z); edge[x].push_back(y); edge[y].push_back(x); //双向存图 if (length[x][y] == -1) length[x][y] = length[y][x] = z; else length[x][y] = length[y][x] = min(z,length[x][y]); } dijkstra(); printf ("%d\n",dis[n] == INF ? -1 : dis[n]); return 0; } /* 测试数据 7 10 1 3 3 1 4 1 3 4 1 2 3 5 3 5 5 4 5 2 3 6 2 5 6 1 5 7 7 6 7 4 */
