题意

给出图，从点1出发，求到最后一个点的时间。

思路

单源最短路，没什么好说的。注意读入的时候的技巧。

代码

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int INF = 1000000000; const int maxn = 110; int n; int edge[maxn][maxn]; int d[maxn]; bool used[maxn]; void dijkstra(int s) { d[s] = 0; while(true) { int v = -1; for(int i = 1 ; i <= n ; i ++) { if(!used[i]) { if(v == -1 || d[i] < d[v]) v = i; } } if(v == -1) break; used[v] = true; for(int i = 1 ; i <= n ; i ++) { d[i] = min(d[i],d[v]+edge[v][i]); } } } int main() { //freopen("in.txt","r",stdin); fill(d,d+maxn,INF); memset(used,false,sizeof(used)); for(int i = 0 ; i < maxn ; i ++) { fill(edge[i],edge[i]+maxn,INF); edge[i][i] = 0; } scanf("%d",&n); for(int i = 2 ; i <= n ; i ++) { for(int j = 1 ; j < i ; j ++) { int tmp; char getit; if(scanf("%d",&tmp)) edge[i][j] = edge[j][i] = tmp; else scanf("%c",&getit); } } dijkstra(1); int ma = d[1]; for(int i = 2 ; i <= n ; i ++) { ma = max(d[i],ma); } cout << ma << endl; return 0; }