2387 poj Til the Cows Come Home【dijkstra，经典&&基础】

野性酷女 2022-08-09 13:57 21阅读 0赞

Til the Cows Come Home

<table> 
 <tbody> 
  <tr> 
   <td> <p><strong>Time Limit:</strong> 1000MS</p> </td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 37068</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 12622</td> 
  </tr> 
 </tbody> 
</table>

Sample Input

5 5
    1 2 20
    2 3 30
    3 4 20
    4 5 20
    1 5 100

Sample Output

题目大意：

给两个数 T , M 。T表示在接下来有T条边【即T行数据】，N表示有N个点，然后输入数据【注意1，重边时，取更短的】【注意2，数组开大点，笔者应为只开到100+，re了3次】，然后输出点 1 到点 N 的最小距离。

#include <cstdio>
    #include <cstring>
    #define INF 1000000
    using namespace std;
    
    int t, n;
    int dis[1001], vis[1001];
    int map[1001][1001];			//数组开到1001就够了，之前笔者只开到 101 ，所以就re了3次 
    
    void Dijsktra() {
    	for(int i = 1; i <= n; i++) {
    		vis[i] = 0;
    		dis[i] = INF;
    	}
    	dis[1] = 0;
    	while(1) {
    		int v = -1;
    		for(int i = 1; i <= n; i++)
    			if(!vis[i] && (v == -1 || dis[v] > dis[i]))
    				v = i;
    		if(v == -1)				//注意这句，没了就成死循环了 
    			break;
    		vis[v] = 1;
    		for(int i = 1; i <= n; i++)
    			if(dis[i] > dis[v] + map[v][i])
    				dis[i] = dis[v] + map[v][i];
    	}
    	printf("%d\n", dis[n]);
    }
    
    int main() {
    	int a, b, c;
    	while(~scanf("%d %d", &t, &n)) {			//注意T为边数，N为点数 
    		for(int i = 1; i <= n; i++)
    			for(int j = 1; j <= n; j++)
    				map[i][j] = (i == j ? 0 : INF);
    		for(int i = 0; i < t; i++) {
    			scanf("%d %d %d", &a, &b, &c);
    			if(map[a][b] > c)					//重边取短的 
    				map[a][b] = map[b][a] = c;
    		}
    		Dijsktra();
    	}
    	return 0;
    }