caaaa-a / 1 Goto Github PK

    for(k=1;k<=n;k++)  
    for(i=1;i<=n;i++)  
    for(j=1;j<=n;j++)  
    if(e[i][j]>e[i][k]+e[k][j])  
          e[i][j]=e[i][k]+e[k][j];

int mincircle = infinity;
Dist = Graph;

for(int k=0;k<nVertex;++k){
    //新增部分:
    for(int i=0;i<k;++i)
        for(int j=0;j<i;++j)
            mincircle = min(mincircle,Dist[i][j]+Graph[j][k]+Graph[k][i]);
    //通常的 floyd 部分:
    for(int i=0;i<nVertex;++i)
        for(int j=0;j<i;++j){
            int temp = Dist[i][k] + Disk[k][j];
            if(temp < Dist[i][j])
                Dist[i][j] = Dist[j][i] = temp;
        }
}

#include <iostream>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 150;
int n,m,a,b,c;
int mp[maxn][maxn];//表示的正常从u到v经过k的最短路
int A[maxn][maxn];//表示的是不经过k的时候回来的时候的最短路
int floyd()
{
   int retmin = INF;
   for(int k = 1;k <= n;k++)
   {
       for(int i = 1;i < k;i++)//假设k为最大的结点，进行遍历优化，并且最后也不会包含最大的结点n
       {
           for(int j = i + 1;j < k;j++)
           {
               //为什么不更新优化mp数组呢，是因为这是一个暴力的循环，总能够找到最小值！
               int tmp = A[i][j] + mp[i][k] + mp[k][j];
               //这个时候A[i][j]还没有更新k结点！！因为下一层才开始更新……
               if(tmp < retmin)retmin = tmp;
           }
       }
       for(int i = 1;i <= n;i++)
       {
           for(int j = 1;j <= n;j++)
           {
               if(A[i][j] > A[i][k] + A[k][j])
                   A[i][j] = A[i][k] + A[k][j];
           }
       }
   }
   return retmin;
}
int main()
{
   int i,j;
   while(~scanf("%d%d",&n,&m))
   {
       //初始化
       for(int i = 1;i <= n;i++)
       {
           for(int j = 1;j <= n;j++)
           {
               mp[i][j] = A[i][j] = INF;
           }
       }
       //输入距离进行更新，防止重边的影响，自动定义为双向边
       for(int i = 1;i <= m;i++)
       {
           scanf("%d%d%d",&a,&b,&c);
           mp[a][b] = mp[b][a] = A[a][b] = A[b][a] = min(mp[a][b],c);
       }
       //进行floyd算法，寻找最小环
       int s = floyd();
       if(s == INF)
           printf("It's impossible.\n");
       else
           printf("%d\n",s);
   }
   return 0;

void floyd()
{
    for(int k = 0; k < n; k ++){ //作为循环中间点的k必须放在最外一层循环 
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++){
                if(dist[i][j] > dist[i][k] + dist[k][j]){
                    dist[i][j] = dist[i][k] + dist[k][j];    //dist[i][j]得出的是i到j的最短路径 
                }     
            }    
        }    
    }    
}

void dijkstra(int s)   //s是起点
{
    memset(visit, false, sizeof(visit));    
    visit[s] = true;
    for(int i = 0; i < n; i ++){
        dist[i] = graph[s][i];
    }
     
    int index;
    for(int i = 1; i < n; i ++){
        int mincost = INF;
        for(int j = 0; j < n; j ++){
            if(!visit[j] && dist[j] < mincost){
                mincost = dist[j];
                index = j;    
            }    
        }
        visit[index] = true;
        for(int j = 0; j < n; j ++){
            if(!visit[j] && dist[j] > dist[index] + graph[index][j]){
                dist[j] = dist[index] + graph[index][j];
            }    
        }    
    }
}

    #define maxvex 100
    typedef struct
    {
    char vexs[maxvex];
    int arc[maxvex][maxvex];
    int vertex,edges;
    }MGraph;

    #define maxvexs 100
    #define infinity 65535//用65535来表示∞
    typedef struct
    {
        char vexs[maxvexs];
        int arc[maxvexs][maxvexs];
        int vertexes,edges;
    }mgraph;

    void creatgraph(mgraph *g)
    {
        int i,j,k,w;
        printf("输入顶点数和边数:\n");
        scanf("%d,%d",&g->vertexes,&g->edges);
        for(i=0;i<g->vertexes;i++)//读入顶点信息，建立顶点表
            scanf("%c",&g->vexs[i]);
        for(i=0;i<g->vertexes;i++)
            for(j=0;j<g->vertexes;j++)
                g->arc[i][j]=infinity;//初始化邻接矩阵
        for(k=0;k<g->vertexes;k++)//读入edges条边，建立邻接矩阵
        {
            printf("输入边(Vi,vj)上的下标i，下标j,和权w:\n");
            scanf("%d%d%d",&i,&j,&w);
            g->arc[i][j]=w;
            g->arc[j][i]=w;//无向图，矩阵对称
        }
    }

    typedef struct EdgeNode
    {
        int adjvex; //邻接点域，存储该顶点对应的下标
        int weight; //用于存储权值，对于非网图可以不需要
        struct EdgeNode *next;  //链域，指向下一个邻接点
    }EdgeNode;//边表结点

    typedef struct VertexNode //顶点表结点
    {
        char data; //顶点域，存储顶点信息
        EdgeNode *firstedge; //边表头指针
    }VertexNode,AdjList[MAXVEX];

    typedef struct
    {
        AdjList adjList;
        int numVertexes,numEdges;//图中当前顶点数和边数
    }GraphAdjList;

    struct Edge{
        int s;
        int e;
        int length;
    }Edge[100];

int dis[maxn];
bool visit[maxn];
int n,m;   //V,E
    void Dijkstra( int s )
    {
        int i,v,u;
        for( i=1; i<=n; ++i )
        {
            visit[i]=false;
            dis[i]=mp[1][i];
        }
        dis[s]=0;
    while( true )
    {
        v=-1;
        for( u=1; u<=n; ++u )
            if( !visit[u] && ( v==-1 || dis[u]<dis[v]) )
                v=u;
        if( v==-1 ) break;
        visit[v]=true;
 
 
        for( u=1; u<=n; u++ )
            dis[u]= min( dis[u],dis[v]+mp[v][u] );
    }
}

#include <iostream>  
#include <cstdio>  
#include <queue>  
#include <vector>  
using namespace std;  
const int Ni = 10000;  
const int INF = 1<<27;  
struct node{  
    int x,d;  
    node(){}  
    node(int a,int b){x=a;d=b;}  
    bool operator < (const node & a) const  
    {  
        if(d==a.d) return x<a.x;  
        else return d > a.d;  
    }  
};  
vector<node> eg[Ni];  
int dis[Ni],n;  
void Dijkstra(int s)  
{  
    int i;  
    for(i=0;i<=n;i++) dis[i]=INF;  
    dis[s]=0;  
    //用优先队列优化  
    priority_queue<node> q;  
    q.push(node(s,dis[s]));  
    while(!q.empty())  
    {  
        node x=q.top();q.pop();  
        for(i=0;i<eg[x.x].size();i++)  
        {  
            node y=eg[x.x][i];  
            if(dis[y.x]>x.d+y.d)  
            {  
                dis[y.x]=x.d+y.d;  
                q.push(node(y.x,dis[y.x]));  
            }  
        }  
    }  
}  
int main()  
{  
    int a,b,d,m;  
    while(scanf("%d%d",&n,&m),n+m)  
    {  
        for(int i=0;i<=n;i++) eg[i].clear();  
        while(m--)  
        {  
            scanf("%d%d%d",&a,&b,&d);  
            eg[a].push_back(node(b,d));  
            eg[b].push_back(node(a,d));  
        }  
        Dijkstra(1);  
        printf("%d\n",dis[n]);  
    }  
    return 0;  
}  
/* 
6 6 
1 2 2 
3 2 4 
1 4 5 
2 5 2 
3 6 3 
5 6 3 
*/