最短路

向右看齐 2024-02-18 22:54 61阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> <h2>最短路</h2> Time Limit: 5000/1000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 88731&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 38407 &nbsp; Problem Description 在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？ &nbsp; &nbsp; &nbsp; Input 输入包括多组数据。每组数据第一行是两个整数N、M（N&lt;=100，M&lt;=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1&lt;=A,B&lt;=N,1&lt;=C&lt;=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。 输入保证至少存在1条商店到赛场的路线。 &nbsp; &nbsp; Output 对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间 &nbsp; &nbsp; Sample Input <pre>&nbsp;</pre> 2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0 &nbsp; &nbsp; Sample Output <pre>&nbsp;</pre> 3 2 &nbsp; &nbsp; Source <a href="http://acm.hdu.edu.cn/search.php?field=problem&amp;key=UESTC+6th+Programming+Contest+Online&amp;source=1&amp;searchmode=source" rel="nofollow">UESTC 6th Programming Contest Online </a> &nbsp; &nbsp; Recommend </td> 
 </tr> 
 </tbody> 
</table>

\#include<iostream> 
\#include<string.h> 
\#include<algorithm> 
\#include<cstdio> 
using namespace std; 
int map\[1001\]\[1001\],low\[10001\],pre\[10001\]; 
struct kk 
\{ 
int s,e,w; 
\}s\[10001\]; 
int DJS(int ve,int n) 
\{ 
 
bool v\[10001\]; 
int i,j; 
for(i=1;i<=n;i++) 
\{ 
low\[i\]=map\[ve\]\[i\]; 
v\[i\]=false; 
if(low\[i\]==0x3f3f3f3f) 
pre\[i\]=-1; 
else 
pre\[i\]=ve; 
\} 
low\[ve\]=0; 
v\[ve\]=true; 
for(i=2;i<=n;i++) 
\{ 
int min=0x3f3f3f3f,pos=ve; 
for(j=1;j<=n;j++) 
\{ 
if(!v\[j\]&&low\[j\]<min) 
\{ 
 
min=low\[j\]; 
pos=j; 
\} 
\} 
 
v\[pos\]=true; 
for(j=1;j<=n;j++) 
\{ 
if(!v\[j\]&&map\[pos\]\[j\]<0x3f3f3f3f) 
\{ 
if(low\[pos\]+map\[pos\]\[j\]<low\[j\]) 
\{ 
low\[j\]=low\[pos\]+map\[pos\]\[j\]; 
pre\[j\]=pos; 
\} 
\} 
\} 
\} 
return low\[n\]; 
\} 
int main() 
\{ 
//freopen("1.txt","r",stdin); 
int n,m,i,j,t=0,k,v0,ve; 
while(~scanf("%d%d",&n,&m),n||m) 
\{ 
k=0; 
int max=0; 
memset(map,0x3f3f3f3f,sizeof(map)); 
memset(s,0x3f3f3f3f,sizeof(s)); 
 
for(i=1;i<=m;i++) 
\{ 
scanf("%d%d%d",&s\[i\].s,&s\[i\].e,&s\[i\].w); 
if(s\[i\].w<map\[s\[i\].s\]\[s\[i\].e\]) 
\{ 
map\[s\[i\].s\]\[s\[i\].e\]=map\[s\[i\].e\]\[s\[i\].s\]=s\[i\].w; 
\} 
\} 
cout<<DJS(1,n)<<endl; 
\} 
return 0; 
\}