cpp1.cpp

提供图的邻接矩阵

#include <iostream> 
#include <fstream> 
#include <iomanip> 
#include <cmath> 
#include <algorithm> 

using namespace std; 

ifstream fin("Dijistra.in"); 

#define NN 1000 // Dijistra求有向图（map[n][n])中点s到其于顶点 的最短路。 
// 数组d[n]存储最终结果。 flag[n]是标志数组。 

int n,m,s; // n为顶点数，m为边数，s为起点。 
int map[NN][NN],flag[NN],d[NN]; // 一律以0为起始单元。 

void dijistra(int s); 
int getmin(); 
void in(); 
int main() 
{ 
in(); 
dijistra(s); 

getchar(); 
fin.close(); 
return 0; 
} 
void dijistra(int s) 
{ 
    int i,j,k; 
     memset(flag,0,sizeof(flag)); 
     memset(d,0,sizeof(d)); 
     for (i=0;i<n;i++) 
    if (map[s]!=0) 
    d[i]=map[s][s]; 
    d[s]=0; 
    flag[s]=1; 

    for (;;){ 
    k=getmin(); 
    flag[k]=1; 
    if (k==-1) break; 
    for (i=0;i<n;i++) 
    if (map[k]  && (d==0 || d>d[k]+map[k]))
		d[k]=d[k]+map[k][i]; 
} 

//out 
    cout<<"s= "<<s<<endl; 
    for (i=0;i<n;i++) 
     cout<<"d [ "<<i<<" ]= "<<d<<endl; 

     return; 
} 
int getmin() 
{ 
  int i,rec=-1; 
   for (i=0;i<n;i++) 
      if (!flag) 
        if (d!=0) 
           if (rec==-1) rec=i; 
           else 
             if ( d[rec] > d[i]) rec=i; 
    return rec; 


} 
void in() 
{ 
   int i,x,y,dist; 
   fin>>n>>m; 
   memset(map,0,sizeof(map)); 
   for (i=0;i<m;i++){ 
   fin>>x>>y>>dist; 
   map[x][y]=dist; 
} 
   fin>>s; 
   return; 
}