最短路径问题，我用的是临接表来存储各个边的信息，用优先队列的dijkstra算法

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=101;const int INF=2<<20;struct edge {	int po,w;	edge * next;};struct node{	edge * first;}head[maxn];typedef pair
       
        pii;priority_queue
        
         
          ,greater
          
            >q;int n,per,minx;void dijkstra(){ int low[maxn],i,j,visit[maxn]; minx=INF; for(i=1;i<=n;i++) { int max=-1; int tot=0; for(j=1;j<=n;j++) { low[j]=j==i?0:INF; visit[j]=0; } q.push(make_pair(low[i],i)); while(!q.empty()) { pii u=q.top(); q.pop(); int x=u.second; if(visit[x]) continue; visit[x]=1; tot++; if(low[x]>max) max=low[x]; edge * tem=head[x].first; while(tem!=NULL) { if(low[tem->po]>(low[x]+tem->w)) { low[tem->po]=low[x]+tem->w; q.push(make_pair(low[tem->po],tem->po)); } tem=tem->next; } } if(tot==n) { if(max
           
            >n&&n!=0) { int i,t,e,w; for(i=1;i<=n;i++) head[i].first=NULL; edge * tem; for(i=1;i<=n;i++) { cin>>t; while(t--) { cin>>e>>w; tem=new edge; tem->po=e; tem->w=w; tem->next=head[i].first; head[i].first=tem; } } dijkstra(); cout<
            
             <<" "<
             
              <