作者：纠结的狂欢_583 | 来源：互联网 | 2023-10-12 00:18
hhh,写板子专用题。。畅通工程续TimeLimit:30001000MS(JavaOthers)MemoryLimit:3276832768K(JavaOthers)Total
hhh,写板子专用题。。
畅通工程续
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 58019 Accepted Submission(s): 21811
Problem Description
某省自从实行了很多年的畅通工程计划后&＃xff0c;终于修建了很多路。不过路多了也不好&＃xff0c;每次要从一个城镇到另一个城镇时&＃xff0c;都有许多种道路方案可以选择&＃xff0c;而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在&＃xff0c;已知起点和终点&＃xff0c;请你计算出要从起点到终点&＃xff0c;最短需要行走多少距离。
Input
本题目包含多组数据&＃xff0c;请处理到文件结束。
每组数据第一行包含两个正整数N和M(0 接下来是M行道路信息。每一行有三个整数A,B,X(0<&＃61;A,B 再接下一行有两个整数S,T(0<&＃61;S,T
Output
对于每组数据&＃xff0c;请在一行里输出最短需要行走的距离。如果不存在从S到T的路线&＃xff0c;就输出-1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
Author
#include
#include
#include
#include
#include
using namespace std;
#define N 10005
#define inf 0x3f3f3f3f
struct Edge{int v,dis;friend bool operator<(Edge a,Edge b){if(a.dis&＃61;&＃61;b.dis)return a.v};
vectorV[N];
int dis[N];
void init()
{for(int i&＃61;0;i}
void _Add(int u,int v,int w)
{V[u].push_back(Edge(v,w));
}
void Add_Edge(int u,int v,int w)
{_Add(u,v,w);_Add(v,u,w);
}
int Dijkstra(int Start,int End)
{priority_queueQ;dis[Start]&＃61;0;Q.push(Edge(Start,0));while(!Q.empty()){Edge u &＃61; Q.top();Q.pop();for(int i&＃61;0;iv.dis&＃43;u.dis){dis[v.v]&＃61;v.dis&＃43;u.dis;Q.push(Edge(v.v,dis[v.v]));}}}return dis[End]&＃61;&＃61;inf?-1:dis[End];
}
int main()
{int n,m;while(~scanf("%d%d",&n,&m)){int u,v,w;init();for(int i&＃61;0;i}
京公网安备 11010802041100号