哈理工oj 1348 最短路径 （floyd算法）

<p>最短路径 </p><p>Time Limit: 1000 MS Memory Limit: 32767 K </p><p>Total Submit: 208(28 users) Total Accepted: 31(20 users) Rating:  Special Judge: No 
 
Description 
给出一个有向带权图G，针对该图有如下的两种操作：
（1）标记该图的一个点
（2）找到两点间的只通过已标记点的最短路径长度</p><p>
输入：
输入包括多组测试，每组测试中第一行包括三个整数N，M，Q，N表示图中的节点数量，N<=300，
M表示边的数量，M<=100000;Q表示执行多少次操作，Q<=100000，所有点被编号为0,1,2,...,N-1，
最初所有的点都是未标记的，接下来M行每行包括三个整数x,y,c,表示从x到y有一条边长度为c,c>0，然
后为Q行，每行表示一次操作，0 x表示将点x标记，1 x y表示查找x到y的只通过已标记点的最短路径长度，
N=M=Q=0是输入结束。</p><p>
输出：</p><p>
输出以一行"Case #:"开始，#表示为第几组测试，从1开始
对于0 x操作，如果x已经被标记过了，输出"ERROR! At point x".
对于1 x y操作，如果x或y没有被标记过，输出"ERROR! At path x to y"，如果无法从x通过标记过的节
点到达y,输出"No such path"，否则输出要求的最短路径长度，每组测试后有一个空行。 
Input 
输入包括多组测试，每组测试中第一行包括三个整数N，M，Q，N表示图中的节点数量，N<=300，
M表示边的数量，M<=100000;Q表示执行多少次操作，Q<=100000，所有点被编号为0,1,2,...,N-1，
最初所有的点都是未标记的，接下来M行每行包括三个整数x,y,c,表示从x到y有一条边长度为c,c>0，然
后为Q行，每行表示一次操作，0 x表示将点x标记，1 x y表示查找x到y的只通过已标记点的最短路径长度，
N=M=Q=0是输入结束。
 </p><p>
 
Output 
输出以一行"Case #:"开始，#表示为第几组测试，从1开始
对于0 x操作，如果x已经被标记过了，输出"ERROR! At point x".
对于1 x y操作，如果x或y没有被标记过，输出"ERROR! At path x to y"，如果无法从x通过标记过的节
点到达y,输出"No such path"，否则输出要求的最短路径长度，每两组测试之间有一个空行。</p><p> </p><p> 
Sample Input 
5 10 10
1 2 6335
0 4 5725
3 3 6963
4 0 8146
1 2 9962
1 0 1943
2 1 2392
4 2 154
2 2 7422
1 3 9896
0 1
0 3
0 2
0 4
0 4
0 1
1 3 3
1 1 1
0 3
0 4
0 0 0
 
Sample Output </p><p>Case 1:
 ERROR! At point 4
 ERROR! At point 1
 0
 0
 ERROR! At point 3
 ERROR! At point 4</p><p> </p><p>要懂得floyd算法原理，对每个顶点 所有边都要松弛一遍，那么这是在所有边都可访问的情况下。对于这个题目，可以每次标记一个点，都以这个点为中心松弛所有边</p><p> </p><p>[cpp] view plaincopy 
</p>
           

#include<iostream>
#include<string.h>
using namespace std;
const int INF=304;
int G[INF][INF];
int vis[INF];

int main()
{
    int n,m,q;
    int u,v,w,cse=1;
    while(cin>>n>>m>>q,n+m+q)
    {
        memset(G,0x1f,sizeof(G));
        memset(vis,0,sizeof(vis));
        for(int i=0; i<=n; i++)
            G[i][i]=0;
        for(int i=0; i<m; i++)
        {
            cin>>u>>v>>w;
            G[u][v]=G[u][v]>w?w:G[u][v];
        }
        cout<<"Case "<<cse++<<":\n";
        int x,y,z;
        for(int i=0; i<q; i++)
        {
            cin>>x;
            if(x)
            {
                cin>>y>>z;
                if(!vis[y]||!vis[z])
                {
                    cout<<"ERROR! At path "<<y<<" to "<<z<<endl;
                }
                else if(G[y][z]>=0x1f1f1f1f)
                {
                    cout<<"No such path"<<endl;
                }
                else
                    cout<<G[y][z]<<endl;
            }
            else
            {
                cin>>y;
                if(vis[y])
                {
                    cout<<"ERROR! At point "<<y<<endl;
                }
                else
                {
                    vis[y]=1;
                    for(int i=0; i<n; i++)
                    {
                        for(int j=0; j<n; j++)
                        {
                            if(G[i][y]+G[y][j]<G[i][j])
                            {
                                G[i][j]=G[i][y]+G[y][j];
                            }
                        }
                    }
                }
            }
        }
        cout<<endl;
    }
    return 0;
}